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..

# Prime Factorization

```
// 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;
}
```

GeniusDex 0 Newbie Poster

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.