// 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");
}
}