3
$\begingroup$

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.

  • 0
    Sieve of Eratosthenes2012-09-04

3 Answers 3

2

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.

0

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

  • 0
    I want to calculate total number of divisors of n which are also divisible by k without calculating prime factorization twice.2012-09-04
0

I use this method in recriprocal tables, like the sumerian 2:30 48 (which multiply to 60).

http://z13.invisionfree.com/DozensOnline/index.php?showtopic=782&view=findpost&p=22089607

This code looks for all of the numbers whose prime factors are a known set (listed in the code with longish logs), that fall below some $b^{n+1}$. So, for example, given "prime 10 3", it would print all of the mantissa (once for 2, 20, 200, 2000, etc), of numbers of the form $2^a 5^b$, under 1000.

The output is sorted at the first or fifth column, to get a simple list (eg 1, 2, 4, 5, 8, 16, 25, 27, ...), or interspersed decimally (1, 1.6, 2, 2.5, 3.2, 4, ...).

It's designed to handle largish numbers, but the outputs can be quite large if there are lots of divisors, eg $510510 , 3$ produces a file over 1.6 million rows, and 150 MB.

The code can be modified to restrict it to divisors of $N$, rather than to be let run through the maximum allowable. For example, the limits are set with the routine crd2log(), but one can select values from am array of divisor-powers of $N$.

Suitable output from this has been used elsewhere in the quoted thread, to find interesting numbers about bases.