# 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

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. Jul 11, 2011 at 17:08
• 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\:$? Jul 11, 2011 at 17:17
• Sorry for lack of explaination. I want to exclude all divisors which are divisible by $p$ from $S$ Jul 11, 2011 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$ Oct 10, 2011 at 14:55
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\}$?