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$.