Paste Search Dynamic
Recent pastes
findAllPrimeFactors
  1. #include <iostream>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <vector>
  5. #include <map>
  6. #include <iterator>
  7.  
  8. using namespace std;
  9. //the primefactors class
  10. class P
  11. {
  12. private:
  13.     static const int max = 300000;
  14.     bool *m_primesSieve;
  15.     int m_primesArray[max/10];
  16.  
  17.     void createPrimeSieve();
  18.     bool checkPrime(int number) const { return m_primesSieve[number];}
  19.     bool findAllPrimeFactors(int number);
  20.  
  21. public:
  22.     P();
  23.     ~P() { delete [] m_primesSieve; }
  24.  
  25.     int findFirstFourConsecutiveIntegers();
  26. };
  27.  
  28. P::P()
  29. {
  30.     m_primesSieve = new bool [max+1];
  31.  
  32.     createPrimeSieve();
  33.  
  34.     int i = 0;
  35.  
  36.     for (int number=2; number<max; number++)
  37.     {
  38.         if(true == checkPrime(number))
  39.         {
  40.            m_primesArray[i++] = number;
  41.         }
  42.     }
  43. }
  44.  
  45. // create a primeSieve of Eratosthenes max value
  46. //also declares the boolean function
  47. void P::createPrimeSieve()
  48. {
  49.  
  50.     memset(m_primesSieve, true, (max+1)*sizeof(bool));
  51.  
  52.     m_primesSieve[0] = m_primesSieve[1] = false;
  53.  
  54.     for (int i=2; i<=(int)sqrt((double)max); i++)
  55.     {
  56.         if (true == m_primesSieve[i])
  57.         {
  58.             for (int j=i*i; j<max; j+=i)
  59.             {
  60.                 m_primesSieve[j] = false;
  61.             }
  62.         }
  63.     }
  64. }
  65.  
  66. bool P::findAllPrimeFactors(int number)
  67. {    
  68.     map<int, int> primeFactors_mp;
  69.     int prime_factor;
  70.     int i= 0;
  71.  
  72.     while (number > 1)
  73.     {
  74.         prime_factor = m_primesArray[i];
  75.  
  76.         while(number % prime_factor == 0)
  77.         {
  78.             primeFactors_mp[prime_factor]++;
  79.             number /= prime_factor;
  80.         }
  81.         i++;
  82.     }
  83.    
  84.     map<int, int>::iterator iter;
  85.     int numOfPrimeFactors = 0;
  86.     for (iter = primeFactors_mp.begin();iter != primeFactors_mp.end(); iter++)
  87.     {
  88.         if (primeFactors_mp[iter->first])
  89.         {
  90.             numOfPrimeFactors++;
  91.         }
  92.     }
  93.  
  94.     if (4 == numOfPrimeFactors)
  95.     {
  96.         return true;
  97.     }
  98.     return false;
  99. }
  100.  
  101. int P::findFirstFourConsecutiveIntegers()
  102. {
  103.     for(int n=2*3*5*7; n<max; n++)
  104.     {
  105.         if ((false == checkPrime(n)) &&
  106.             (true  == findAllPrimeFactors(n)) &&
  107.             (true  == findAllPrimeFactors(n+1)) &&
  108.             (true  == findAllPrimeFactors(n+2)) &&
  109.             (true  == findAllPrimeFactors(n+3)))
  110.         {
  111.                 int four_cons[4];
  112.                         four_cons[0]= n;
  113.                         four_cons[1]= n+1;
  114.             four_cons[2]= n+2;
  115.             four_cons[3]= n+3;
  116.            
  117.             return *four_cons;
  118.         }
  119.     }
  120.     return 0;
  121. }
  122. //declares the main function
  123. int main()
  124. {
  125.     P p;
  126. //declares the integer n
  127.     int n = p.findFirstFourConsecutiveIntegers();
  128. //prints out the 4 consecutive integers
  129.         cout<<n<<endl;
  130.         cout<<n+1<<endl;
  131.         cout <<n+2<<endl;
  132.         cout<<n+3<<endl;
  133.  
  134.     return 0;
  135. }
  136.  
Parsed in 0.027 seconds