Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer 1

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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