Start New Discussion within our Software Development Community

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.