Robson » Code » C++ » Prime Factors

 
// prime factor finder v1.0
 
#include <stdio.h>
// primes will be generated up to this number
// make sure this is just above the highest number you want prime factors of
#define MAX_PRIMES 50
 
int primes[MAX_PRIMES];
int p_count = 2;
 
int prime_numbers()
{
    bool bPrime, bSwitch = false;
    primes[0] = 2;
    primes[1] = 3;    
    for (int a = 5; a <= MAX_PRIMES; a+=2)
    {
         bPrime = true;
         for (int b = 0; b < p_count; b++)
         {
              if (primes[b] * primes[b] > a)
                   break;
              if (!(a % primes[b]))
              {
                   bPrime = false;
                   break;
              }  
         }          
         if (bPrime)
              primes[p_count++] = a;
         if (bSwitch)
              a+=2;
         bSwitch = !bSwitch;
    }
}
 
void prime_factors(int n, int factors[], int& count)
{
    int sd;
    if (n <= 3)
    {
          factors[0] = n;
          count = 1;
    }
    else
    {
         while (n > 1)
         {
              for (sd = 0; sd < p_count && n % primes[sd]; sd++);
              n /= primes[sd];
              factors[count++] = primes[sd];
         }
    }
}
   
// * example use - print prime factors of numbers 1 to 20 * //
int main()
{
    int i, count, factors[100];
    prime_numbers();
    for (int n = 1; n <= 20; n++)
    {
         count = 0;
         prime_factors(n, factors, count);
         printf("%d =", n);
         for (i = 0; i < count; i++)
              printf(" %d", factors[i]);
         printf("\n");
    }
}