2
$\begingroup$

I am looking for an efficient algorithm to find the number of divisors for all numbers in a huge range up to $10^9$.

Such a task is presented in these two problems: NDIV, and spoj NFACTOR

I used prime factorization to find the number of divisors for each number in the specified range using the following c++ code:

#include <iostream>
using namespace std;

int fact(int x) {
    int sum = 0;
    for (int i = 0, ln = prime.size(); i < ln && prime[i] * prime[i] <= x;
            ++i) {
        for (sum += (x % prime[i] == 0); x % prime[i] == 0; x /= prime[i])
            ;
        if (sum > 10)
            return 11;
    }
    sum += (x > 1);
    return sum;
}

int main() {
    // your code goes here
    return 0;
}

Where "prime" is an array with all prime numbers up to $10^9$, calculated using Sieve of Eratosthenes algorithm.

$\endgroup$
  • $\begingroup$ I hope you're familiar with number of divisors function $\tau$ $\endgroup$ – ganeshie8 Aug 29 '14 at 0:37
  • $\begingroup$ yes I am and i used it to solve the above problems $\endgroup$ – Yousef Hadder Aug 29 '14 at 17:57
  • $\begingroup$ stackoverflow.com/questions/9168579/… $\endgroup$ – Michael Stocker Sep 3 '14 at 12:38
  • $\begingroup$ I suppose Hugh Rang is not an actor that we never heard of, but a "huge range"? $\endgroup$ – gnasher729 Aug 10 '16 at 21:50
1
$\begingroup$

So your question is not: "Given an integer x ≥ 1, how many divisors does x have". Your question is: "Given an integer n ≥ 1, and two integers A ≤ B, how many integers x, A ≤ x ≤ B, have exactly n divisors".

The trivial but inefficient solution is calculating the number of divisors of each x in that range.

A better but still inefficient solution will not calculate the number of divisors of each x in that range, but check that x has n divisors: For example, if n = 2, and x is an even number, then there is no need to calculate the number of divisors: An even x has n = 2 divisors if and only if x = 2. That check will sometimes be hard, sometimes easy.

What you really want is to calculate directly how many integers x have n divisors. As others wrote, for example if $x=p^aq^br^c, p,q,r$ prime, the number of factors of $x$ is $(a+1)(b+1)(c+1)$. This is supposed to be equal to n. So first you find all possible ways to write n as a product of integers ≥ 2. Each such product corresponds to a way to write x as the product of primes.

As an example, let n = 8 = 4 * 2 = 2 * 2 * 2. We see that an integer x with exactly 8 divisors has the form $p^7$, $p^3q^1$, or $p^1q^1r^1$ for primes p, q and r. These can be counted reasonably efficiently: You would count the primes p such that A ≤ $p^7$ ≤ B. Then for every prime p with $2p^3 ≤ B$, you count the primes q such $A ≤ p^3q ≤ B$. Then for every prime p with $p^3 ≤ B$, and for every prime q > p with $pq^2 ≤ B$, count the primes r > q with $A ≤ pqr ≤ B$. In this particular case n = 8 a sieve of all primes up to $B / 6$ would make the counting quite fast. (Why $B/6$ ? Because you need to count among other things the numbers 6r, for 6r ≤ B or r ≤ B/6).

$\endgroup$
0
$\begingroup$

Are you familiar with the divisor function? If $n=p^aq^br^c, p,q,r$ prime, the number of factors of $n$ is $(a+1)(b+1)(c+1)$ This works for any number of prime factors.

Now take your $N$ and factor it. You can find the patterns of factors that will work. For example, if $N=8$, you can have numbers of the form $p^7,p^3q,$ or $pqr$. The seventh powers are easy to check. For $p^3q$ I would go through the cubes of primes and for each compute the range of $q$ that works, then compute the number of primes in that range. $pqr$ will be the slow one. We can assume $p \lt q \lt r$ but you still have a double loop over primes before finding the range of $r$ that works.

$\endgroup$
  • $\begingroup$ Yes I am familiar with it, in fact this is why i used prime factorization to solve these problems, but it shows that this method is also slow for large input files, this is my full c++ implementation: ideone.com/fL6YdT $\endgroup$ – Yousef Hadder Aug 29 '14 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.