[Math] Number of divisors

divisibility

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.

Best Answer

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.

Related Solutions

Prime Numbers – How to Find the Largest Prime Factor

In general factoring problem is not easy, see:Theoretical Computer Science Q&A
There is a Pollard-Rho algorithm which you can find some information here: Wikipedia: Factoring integers
I solved that problem of Project Euler too! The output of MATLAB is:

   71

   839

        1471

        6857

Elapsed time is 0.002433 seconds.
>>

And the code in MATLAB:

clear;
clc;
tic;
p=600851475143 ;
m=3;
while(sqrt(m)<p)
    j=rem(p,m);
    if (j==0)
        p=p/m;
        disp(m);
        m=m+2;
    else
        m=m+2;
    end
end
toc;

By the way, there is factor command in MATLAB that directly outputs the factors of a number. But it has a 2^32 of input limitation size. I removed the limitation of the original code and it responded in 0.027501 seconds!

[Math] How to find the number of divisors that are perfect squares and divisible by a number

Any perfect square $S$ has even multiplicity of any given prime number, so if it divides $n = 2^{14} 3^{9} 5^{8} 7^{10} 11^{3} 13^{5} 37^{10}$ it in fact must divide $n' = 2^{14} 3^8 5^8 7^{10} 11^2 13^4 37^{10}$ (all exponents rounded down to even). Now if the perfect square $d=2^{2}3^{4}5^{2}11^{2}$ divides $S$, then $S/d$ is integer and still a perfect square, and it divides $n'/S=2^{12}3^45^67^{10}13^4 37^{10}=m$. Then $\sqrt{S/n'}$ is any divisor of $\sqrt m=2^63^25^37^513^237^5$. You can count those divisors. You did. $9072$ is the right answer.

If you've encountered a smaller example where this approach does not give the right answer, why not present the details of that case?

Best Answer

Related Solutions

Prime Numbers – How to Find the Largest Prime Factor

[Math] How to find the number of divisors that are perfect squares and divisible by a number

Related Question