Want more features on Pastebin? Sign Up, it's FREE!
Guest

Primes

By: a guest on Dec 25th, 2011  |  syntax: C++  |  size: 3.22 KB  |  views: 45  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <time.h>
  2. #include <iostream>
  3. #include <vector>
  4. #include <math.h>
  5. using namespace std;
  6.  
  7. const int maxnum=100000;
  8. vector<int> primes1;
  9. vector<int> primes2;
  10. vector<int> primes3;
  11.  
  12. void Primev1();
  13. void Primev2();
  14. void Primev3();
  15.  
  16. int main()
  17. {
  18.     cout<<"Calculating Primes...PSketchy's code with uberdev's  correction"<<endl;
  19.     Primev1();
  20.     cout << "Press enter to continue."<<endl;
  21.     cin.get();
  22.     cout<<"Calculating Primes...Yojay's optimizations + only checking for divisility to sqrt(i)"<<endl;
  23.     Primev2();
  24.     cout << "Press enter to continue."<<endl;
  25.     cin.get();
  26.     cout<<"Calculating Primes...Only checking based on previous primes / up to sqrt(i)"<<endl;
  27.     Primev3();
  28.  
  29.     return 0;
  30. }
  31. void Primev1()
  32. {
  33.     clock_t start, end;
  34.     start = clock();
  35.  
  36.     for (int i = 2; i <= maxnum; i++)
  37.     {
  38.         bool isPrime = true;
  39.         for (int n = 2; n < i; n++)
  40.         {
  41.             if (i%n == 0)
  42.             {
  43.                 // i is divisible by n with no remainder, so it's not a prime
  44.                 isPrime = false;
  45.                 break;
  46.             }
  47.         }
  48.         if (isPrime)
  49.         {
  50.             primes1.push_back(i);
  51.             //cout<< "prime:  " << i << endl;
  52.         }
  53.     }
  54.  
  55.     end = clock();
  56.     cout << "Primes found:"<< primes1.size()<<endl;
  57.     cout << "Time required for execution: "
  58.     << (double)(end-start)/CLOCKS_PER_SEC
  59.     << " seconds." << "\n\n";
  60. }
  61. void Primev2()
  62. {
  63.     clock_t start, end;
  64.     start = clock();
  65.     primes2.push_back(2);//we must initiallize our vector with the prime number of 2 for this method
  66.     //cout<< "prime:  " << 2 << endl;
  67.  
  68.     for (int i = 3; i <= maxnum; i+=2)
  69.     {
  70.         bool isPrime = true;
  71.  
  72.         for (int n = 2; n <= sqrt(i); n++)
  73.         {
  74.             if (i%n == 0)
  75.             {
  76.                 // i is divisible by n with no remainder, so it's not a prime
  77.                 isPrime = false;
  78.                 break;
  79.             }
  80.         }
  81.         if (isPrime)
  82.         {
  83.             primes2.push_back(i);
  84.             //cout<< "prime:  " << i << endl;
  85.         }
  86.     }
  87.  
  88.  
  89.     end = clock();
  90.     cout << "Primes found:"<< primes2.size()<<endl;
  91.     cout << "Time required for execution: "
  92.     << (double)(end-start)/CLOCKS_PER_SEC
  93.     << " seconds." << "\n\n";
  94. }
  95. void Primev3()
  96. {
  97.     clock_t start, end;
  98.     start = clock();
  99.     primes3.push_back(2);//we must initiallize our vector with the prime number of 2 for this method
  100.     //cout<< "prime:  " << 2 << endl;
  101.  
  102.     for (int i = 3; i <= maxnum; i+=2)
  103.     {
  104.         bool isPrime = true;
  105.         for (int j=0; j<primes3.size(); j++)
  106.         {
  107.             if(primes3[j]>sqrt(i))
  108.                 break;
  109.             if(i%primes3[j]==0)
  110.             {
  111.                 // i is divisible by n with no remainder, so it's not a prime
  112.                 isPrime = false;
  113.                 break;
  114.             }
  115.         }
  116.         if (isPrime)
  117.         {
  118.             primes3.push_back(i);
  119.             //cout<< "prime:  " << i << endl;
  120.         }
  121.     }
  122.  
  123.  
  124.     end = clock();
  125.     cout << "Primes found:"<< primes3.size()<<endl;
  126.     cout << "Time required for execution: "
  127.     << (double)(end-start)/CLOCKS_PER_SEC
  128.     << " seconds." << "\n\n";
  129. }
clone this paste RAW Paste Data