# Number of divisors

How can I find number of divisors of N which are not divisible by K.

($2 \leq N$, $k \leq 10^{15})$

One of the most easiest approach which I have thought is to first calculate total number of divisors of 'n' using prime factorization (by Sieve of Eratosthenes) of n and then subtract from it the Number of divisors of the number 'n' that are also divisible by 'k'.

In order to calculate total number of divisors of number n that are also divisible by 'k' I will have to find the total number of divisors of (n/k) which can be also done by its prime factorization.

My problem is that since n and k can be very large, doing prime factorization twice is very time consuming.

Please suggest me some another approach which requires me to do prime factorization once.

-
 Which algorithm are you using for Factorizing the integer? – Quixotic Sep 4 '12 at 10:41 Sieve of Eratosthenes – Snehasish Sep 4 '12 at 11:25

Your idea looks fine. But for integer factorization you can implement Pollard's rho algorithm or even faster Elliptic Curve Method.

You can test your algorithm at here and here.

-

Here is a code in C

int NUM_DIVISORS(int n)
{
int j=0;
int p=0;
if(!(n%2))
{
for(j=2;j<=sqrt(n);j=j+1){
if (!(n%j)){
p = (p+2);
}
if(j*j==n){
p=p-1;
}
}
}//end of if
if(n%2) {
for(j=3;j<=sqrt(n);j=j+2){
if (!(n%j)){
p = p+2;
}
if(j*j==n){
p=p-1;
}
}
}//end of if
p=p+2;
return p;
}//end of function


You can also per-initialize an array of prime numbers up to a certain number, then use it to make your code run faster
Also take a look at my answer

-
 Your code is WRONG. I think you have given me the code of total number of divisors of a number !!! – Snehasish Sep 4 '12 at 15:51 @Snehasish What's wrong with it? I uploaded the code as a hint because you wanted "total number of divisors of 'n'" – PooyaM Sep 4 '12 at 16:01 I want to calculate total number of divisors of n which are also divisible by k without calculating prime factorization twice. – Snehasish Sep 4 '12 at 19:07