Number of divisors

Question

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.

Answer 1

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.

Answer 2

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