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.

Answer 2

You don't cache any of your results: instead you should consider using

map<int,vector<int>> vPrimes

This map would contain all the prime factors of a given number. For example for 50 it would contain 2,5 (2*5*5=50). Then assume you try to compute it for 300 then you test (300%3=0) then you add 3 to the list, resulting in (2,3,5).

Hope that helps,

Answer 3

from wikipedia:

Factorization of large integers is believed to be a computationally very difficult problem, and the security of many modern cryptography systems is based upon its infeasibility.[11]

your best approach is to brute force the prime factors by mean of the Eratosthenes' sieve or pollard-rho algorithm. Because the numbers aren't so big (100000 at max) you could just precompute all the prime factors very quickly on modern hardware. cheers

Answer 4

The main optimization: you don't need to search up to n, you can just search to sqrt(n). Anything remaining is prime. Secondary optimization: divide out primes you find to reduce the bound to which you search.

More could be done but this is about a thousand times faster already.

vector<unsigned long int> find_divisors(const unsigned long int &m) {
  unsigned long int n = m;
  vector<unsigned long int> divisors;
  if (n%2 == 0) {
    divisors.push_back(2);
    while (n%2==0) n/=2;
  }

  for (unsigned long int i = 3; i*i <= n; i += 2) {
      if (n%i) continue;
      divisors.push_back(i);
      while (n%i==0) n/=i;
  }
  if (n > 1) divisors.push_back(n);
  return divisors;
}

Answer 5

For such a limited range of numbers, it is quite acceptable to hard code a table of primes up to 1000.

int P[169]= {
    2,   3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,  41,
   43,  47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97, 101,
  103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
  173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
  241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
  317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
  401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
  479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
  571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
  647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
  739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
  827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
  919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009          
};

int i= 0;
while (i < 169 && P[i] < Number)
{
    if (Number % P[i] != 0)
        i++;
    else
        Number/= P[i]; // P[i] is a factor
}
// Number is the last factor