0
$\begingroup$

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

  • 0
    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$2011-10-10

1 Answers 1

4

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\}$?