Calculating the prime factors of a number

Question

I have the following request:

find the PRIME factors (without their exponents) for a given number n with 2 < n < 999999.

I have the following algorithm that solves the problem, but seems to have some performance issues:

bool is_prime(const unsigned long int &number) {
    for (unsigned long int i = 2; i <= sqrt(number); i++) {
        if (number%i == 0) return false;
    }
    return true;
}
unsigned long int next_prime(unsigned long int current) {
    current++;
    while (!is_prime(current)) {
        current++;
    }
    return current;
}

// THE PROBLEM SOLVER
vector<unsigned long int> find_divisors(const unsigned long int &n) {
    vector<unsigned long int> divisors;
    for (unsigned long int i = 2; i <= n; i = next_prime(i)) {
        if (n%i == 0) divisors.push_back(i);
    }
    return divisors;
}

Issue: for big numbers, the algorithm takes too much time (for the maximum allowed number, it takes about 1.5 seconds).

Examples (that are correct):

• n = 1620 outputs {2, 3, 5}
• n = 2048 outputs {2}
• n = 4096 outputs {2}

Answer 1

Your proposed algorithm is, as you imply, horribly inefficient. But for the stated range, this is a very simple problem for computers with 32-bit integer arithmetic. This is how to do it:

for (int p = 2 ; p * p <= n ; p = (p == 2) ? 3 : (p + 2)) { // p = 2,3,5,7,9,...until p > sqrt(n)
  if (n % p) continue ;
  divisors.push_back (p) ;       // p divides n, so save it
  do n /= p ; while (!(n % p)) ; // Remove all divisors p from n
}
if (n > 1) divisors.push_back (n) ;

I am not going to explain this: you will learn much more by figuring it out for yourself. It could be made a little faster by various micro-optimisations, but it is essentially optimal for your stated range, unless you use prime tables. Such tables might make it a little faster, but in most cases it won't be worth it.