# 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

## 2 Answers

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 2, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9062440395355225, "perplexity_flag": "middle"}