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