# Number of divisors excluding set of primes S

Quite much time ago I found task where I was pleased to compute number of divisors (they are primes!) excluding numbers from set S (in other words, set S should only contain divisors of number N, which is easy). Next I'm doing prime factorization so I receive $N = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}.$
Next number of divisors D of number N is $(a1+1)(a2+1) ... (ak+1)$ and requires number is $D-|S|$

For example we have number N=58 and at beginning 2 elements in the set: $2,3$ 2 divides 58, but 3 doesn't so we have only in set 2. prime factorization of 58 is $2^1+29^1$ so number of divisors D is (1+1)(1+1)=4. Assume that 58 isn't divisor of 58, so we have 3 divisors. Finally, our result is$D-|S|=2$

Today I came up with this solution, but it's too slow approach. Is there any faster? Thanks for any hints, solutions, Math Friend. Cheers Chris

P.S there is link to this task: https://www.spoj.pl/problems/HABLU/

EDIT: Having had a look at the link, I'm going to try to restate the problem in a more standard way. You are given a set $S$ of primes, and a positive integer $N$. You are to find out how many divisors $N$ has, not counting those that are multiples of one or more of the primes in $S$.

-
If $n = p_1^{a_1} \ldots p_n^{a_n}$ and $S = \{p_{i}\}_{i \in I}$ then I think the number of divisors excluding $S$ is $\prod_{i \in \{1, \ldots, n\} \setminus I} (1+a_i)$ (the product of $(1+a_i)$ excluding values $i \in I$). To compute it, divide $n$ by elements of $S$ as long as you can, then compute the number of divisors of the resulting number. –  Joel Cohen Jul 11 '11 at 17:08
Perhaps you didn't notice the line "S only contains primes or 1". –  ShreevatsaR Jul 11 '11 at 17:16
There is ambiguity. Does $\:p\in S\:$ mean that you wish to exclude all divisors divisible by $\:p\:,\:$ or does it mean to exclude only the divisor $\:p\:$? –  Bill Dubuque Jul 11 '11 at 17:17
Sorry for lack of explaination. I want to exclude all divisors which are divisible by $p$ from $S$ –  Chris Jul 11 '11 at 20:49
My previous answer still seems applicable to me. Use your formula $(a_1+1)(a_2+1)\ldots$ including only those $a_i$ that correspond to primes not in $S$ –  Ross Millikan Oct 10 '11 at 14:55

## 1 Answer

If $S$ only has primes, can't you just ignore those primes in the factorization of $N$?. That is, if $n=210=2*3*5*7$ and $S=\{2,3\}$, isn't the answer $4$, being $\{1,5,7,35\}$?

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8431777358055115, "perplexity": 392.21406880707127}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 20, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-32/segments/1438042990123.20/warc/CC-MAIN-20150728002310-00203-ip-10-236-191-2.ec2.internal.warc.gz"}