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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Joel Cohen
    Jul 11, 2011 at 17:08
  • $\begingroup$ Perhaps you didn't notice the line "S only contains primes or 1". $\endgroup$ Jul 11, 2011 at 17:16
  • $\begingroup$ 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\:$? $\endgroup$ Jul 11, 2011 at 17:17
  • $\begingroup$ Sorry for lack of explaination. I want to exclude all divisors which are divisible by $p$ from $S$ $\endgroup$ Jul 11, 2011 at 20:49
  • $\begingroup$ 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$ $\endgroup$ Oct 10, 2011 at 14:55

1 Answer 1

4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.