Abdulg

Prime Factoriser [C++]

Feb 26th, 2014
383
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.64 KB | None | 0 0
  1. /*
  2. Compiled under Debian GNU/Linux using g++
  3. Usage: PrimeFactor Number
  4.  
  5. Released under the epic memes licence
  6. You should have recieved a copy with this, if not: 9gag.com/memes/licence.pptx
  7. */
  8.  
  9. #include<iostream>
  10. #include<vector>
  11. #include<cstdlib>
  12. #include<unistd.h>
  13.  
  14. using namespace std;
  15.  
  16. bool IsPrime (int Number);
  17. vector <int> BubbleSortVector(vector <int> Vector);
  18.  
  19. int main(int argc, const char* argv[])
  20. {
  21.     if (argc != 2)
  22.     {
  23.         cout << "Usage: PrimeFactor Number" << endl;
  24.         return 1;
  25.     }
  26.    
  27.     cout << "Factoring " << atoi(argv[1]) << endl;
  28.     cout.flush();
  29.    
  30.     vector <int> PrimeFactors;
  31.     vector <int> CurrentFactors;
  32.     vector <int> NextFactors;
  33.     bool Done = false;
  34.     bool loob = false; //lol
  35.     int CheckTotal = 1;
  36.    
  37.     CurrentFactors.push_back(atoi(argv[1]));
  38.  
  39.     while (Done == false)
  40.     {
  41.         for (int i = 0; i < CurrentFactors.size(); i++)
  42.         {
  43.             for (int eye = 2; eye < CurrentFactors.at(i) && loob == false; eye++)
  44.             {
  45.                 if (CurrentFactors.at(i) % eye == 0)
  46.                 {
  47.                     if (IsPrime(CurrentFactors.at(i) / eye))
  48.                      PrimeFactors.push_back(CurrentFactors.at(i) / eye);
  49.                     else NextFactors.push_back(CurrentFactors.at(i) / eye);
  50.                    
  51.                     if(IsPrime(eye)) PrimeFactors.push_back(eye);
  52.                     else NextFactors.push_back(eye);
  53.                     loob = true;
  54.                 }
  55.             }
  56.             loob = false;
  57.         }
  58.         CurrentFactors.erase(CurrentFactors.begin(), CurrentFactors.end());
  59.         for (int i = 0; i < NextFactors.size(); i++)
  60.         CurrentFactors.push_back(NextFactors.at(i));
  61.         NextFactors.erase(NextFactors.begin(),NextFactors.end());
  62.         CheckTotal = 1;
  63.         for (int i = 0; i < PrimeFactors.size(); i++)
  64.         CheckTotal = CheckTotal * PrimeFactors.at(i);
  65.         if (CheckTotal == atoi(argv[1])) Done = true;
  66.     }          
  67.     PrimeFactors = BubbleSortVector(PrimeFactors);
  68.    
  69.     cout << "The prime factors of " << atoi(argv[1]) << " are";
  70.     for(int i = 0; i < PrimeFactors.size(); i++) cout << " " << PrimeFactors.at(i) << " ";
  71.     cout << endl << endl;
  72.     return 0;
  73. }
  74.  
  75. bool IsPrime (int Number)
  76. {
  77.     for(int i = 2; i < Number; i++) if(Number % i == 0) return false;
  78.     return true;
  79. }
  80.  
  81. vector <int> BubbleSortVector(vector <int> Vector)
  82. {
  83.     bool Done = false;
  84.     while (Done == false)
  85.     {
  86.         Done = true;
  87.         for (int i = 0; i < Vector.size() - 1; i++)
  88.         {
  89.             if(Vector.at(i) < Vector.at(i+1))
  90.             {
  91.                 int Temp = Vector.at(i+1);
  92.                 Vector.at(i+1) = Vector.at(i);
  93.                 Vector.at(i) = Temp;
  94.                 Done = false;
  95.             }
  96.         }
  97.     }
  98.     return Vector;
  99. }
  100.  
  101. /*
  102. Output:
  103. abdul@debian:~/ProjectEuler$ ./PrimeFactor 8888
  104. Factoring 8888
  105. The prime factors of 8888 are 101  11  2  2  2
  106. */
Advertisement
Add Comment
Please, Sign In to add comment