# Prime Factorization

The program uses an implementation of the Sieve of Eratosthenes to generate a small list of prime numbers which is subsequently used for direct comparison to find the prime factors for any whole number up to and including 478939.
This limitation is due to the primitive method used to generate prime numbers, but it is adequate for doing homework problems for adding fractions etc..

``````// Verified with Dev C++ 4.9.9.2 wx beta 6.7
// Uses an implementation of the Sieve of Eratosthenes
// to generate a small list of prime numbers
// which is subsequently used for direct comparison
// to find the prime factors for any number up to 478939
// This limitation is due to the primitive method
// used to generate prime numbers, but it is adequate
// for doing homework problems for adding fractions etc..

#include <cstdio>
#include <cstdlib>
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

// prototype declarations
void ClearMultiple(unsigned long nElimina, unsigned long integerArray[], unsigned long sizeOfloatArray);

int main()
{
// Enter the number to find prime components
unsigned long nLimit=0;
bool bFlag=false;

while (bFlag == false)
{
cout << "Calculate Prime Factors for what number ? ";
cin >> nLimit;
if ((nLimit > 1)&&(nLimit<=478939)) {bFlag = true;}
}
cout << "\n\n";

// Creates an array of all numbers less than nLimit
// then uses an implementation of the Sieve of Eratosthenes
// to eliminate all repeating multiples
unsigned long inputValues[nLimit];
unsigned long nLoop=0;

for(nLoop = 1; nLoop < nLimit; nLoop++)
{
inputValues[nLoop] = nLoop;
}

for(nLoop = 2; nLoop < nLimit; nLoop++)
{
// Find the next number to eliminate
if (inputValues[nLoop] == nLoop)   // If Loop = Loop then ClearMultiple
{
ClearMultiple(nLoop, inputValues, nLimit);
}   // ... if not continue to the next
}

// After the the Sieve of Eratosthenes is finished
// keep only the numbers remaining i.e. Prime numbers

//This part counts how many numbers were eliminated
unsigned long nAccumalator=0;
for(nLoop = 2; nLoop < nLimit; nLoop++)
{
//if inputValues[Loop] = 0 then Accumalator=Accumalator+1
if (inputValues[nLoop] == 0)
{
nAccumalator++;
}
}

// Qty of prime numbers = nLimit - Accumalator
unsigned long nQta;
nQta = nLimit - nAccumalator;

//Define a new array to keep only the remaining prime numbers
unsigned long nCounter=0;
unsigned long Arrayprimi[nQta];

for(nLoop = 2; nLoop < nLimit; nLoop++)
{
//if InputValue[Loop]= Loop then Accumalator=Accumalator+1
//   ArrayPrimi[Accumalator]=Loop
if (inputValues[nLoop] == nLoop)
{
nCounter++;
Arrayprimi[nCounter] = nLoop;
}
}

//  Test the Number nLimit against the primes we generated
int QtyPrimes=0;
double dDivideTest=1;

// first count how many primes are divisable
// to determine if the number is prime or composite
for(nLoop = 1; nLoop < nQta-1; nLoop++)
{
dDivideTest=(int(nLimit/Arrayprimi[nLoop])* Arrayprimi[nLoop])-nLimit;
if(dDivideTest==0)
{
QtyPrimes++;
}
}

// if it is a prime number then print and quit
if(QtyPrimes==0)
{
cout << nLimit << " is a prime number \n" << endl;

// wait until user is ready before terminating program
// to allow the user to see the program results
system("PAUSE");
return 0;
}

// Now print the divisable primes

//if it a composite number print the factors  and then print their usage
cout << nLimit << " is divisable by the following prime numbers \n" << endl;

//this part determines the factors by testing for even division
int nPrimes[QtyPrimes];
QtyPrimes=0;
for(nLoop = 1; nLoop < nQta-1; nLoop++)
{
dDivideTest=(int(nLimit/Arrayprimi[nLoop])* Arrayprimi[nLoop])-nLimit;
if(dDivideTest==0)
{
QtyPrimes++;
nPrimes[QtyPrimes]=Arrayprimi[nLoop];
cout << "  " << Arrayprimi[nLoop] << endl;
}
}

cout << "\n" << endl;

//this part counts and prints how many times each prime factor is used.
int Qty[QtyPrimes];
int nTemp=nLimit;
int nCount=0;

cout << nLimit << " = ";
for (nLoop=1; nLoop <= QtyPrimes; nLoop++)
{
Qty[nLoop]=0;
dDivideTest=0;
while(dDivideTest==0)
{
dDivideTest=(int(nTemp/nPrimes[nLoop])* nPrimes[nLoop])-nTemp;
if (dDivideTest==0)
{
nTemp=nTemp/nPrimes[nLoop];
Qty[nLoop]++;
}
}
//print the result for each prime
for (nCount=1;nCount <Qty[nLoop];nCount++)
{
cout << nPrimes[nLoop] << "*";
}
//print the prime one more time
// and if there are more primes print another *
cout << nPrimes[nLoop];
if (QtyPrimes>nLoop)
{
cout << "*";
}
}

cout << "\n\n" << endl;

// wait until user is ready before terminating program
// to allow the user to see the program results
system("PAUSE");
return 0;
}

// Function ClearMultiple
// eliminates all multiples from the Array
void ClearMultiple(unsigned long nElimina, unsigned long integerArray[], unsigned long nLimit)
{
unsigned long nA;
for (nA= 2 * nElimina ; nA < nLimit; nA = nA + nElimina)
{
integerArray[nA]=0;
}
return;
}``````

It might be easier to use the following code:

``int q(int n,int*a,int i=2){*a=i;return n>1?n%i?q(n,a,i+1):1+q(n/i,a+1,i):0;}``

it takes 2 arguments on invocation, the first being the number to factorize and the second being en array where all prime factors can be stored. This array should be big enough to hold all possible prime factors. It returns the number q of prime factors put into the given array.

Given the sheer complexity of the above code, my line of code will probably run faster. It is probably limited to the maximal stack size and it will recurse O(n+q) levels deep.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.