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.

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.

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

3 Answers 3

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.

share|improve this answer
add comment

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

share|improve this 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'" –  Zeta.Investigator 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
add comment

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.

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.