0

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