Guest User

Untitled

a guest
Apr 4th, 2021
184
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <chrono>
  2. #include <ctime>
  3. #include <iostream>
  4. #include <bitset>
  5. #include <map>
  6. #include <cstring>
  7. #include <cmath>
  8. #include <vector>
  9.  
  10. using namespace std;
  11. using namespace std::chrono;
  12.  
  13. class prime_sieve
  14. {
  15.   private:
  16.  
  17.       long sieveSize = 0;
  18.       vector<bool> Bits;
  19.       const std::map<const long, const int> myDict =
  20.       {
  21.             {          10L, 4         },                // Historical data for validating our results - the number of primes
  22.             {         100L, 25        },               // to be found under some limit, such as 168 primes under 1000
  23.             {        1000L, 168       },
  24.             {       10000L, 1229      },
  25.             {      100000L, 9592      },
  26.             {     1000000L, 78498     },
  27.             {    10000000L, 664579    },
  28.             {   100000000L, 5761455   },
  29.             {  1000000000L, 50847534  },
  30.             { 10000000000L, 455052511 },
  31.  
  32.       };
  33.  
  34.       bool validateResults()
  35.       {
  36.           if (myDict.end() == myDict.find(sieveSize))
  37.               return false;
  38.           return myDict.find(sieveSize)->second == countPrimes();
  39.       }
  40.  
  41.    public:
  42.  
  43.       prime_sieve(long n)
  44.         : Bits(n, true), sieveSize(n)
  45.       {
  46.       }
  47.  
  48.       ~prime_sieve()
  49.       {
  50.       }
  51.  
  52.       void runSieve()
  53.       {
  54.           int factor = 3;
  55.           int q = sqrt(sieveSize);
  56.  
  57.           while (factor <= q)
  58.           {
  59.               for (int num = factor; num < sieveSize; num += 2)
  60.               {
  61.                   if (Bits[num])
  62.                   {
  63.                       factor = num;
  64.                       break;
  65.                   }
  66.               }
  67.               for (int num = factor * factor; num < sieveSize; num += factor * 2)
  68.                   Bits[num] = false;
  69.  
  70.               factor += 2;
  71.           }
  72.       }
  73.  
  74.       void printResults(bool showResults, double duration, int passes)
  75.       {
  76.           if (showResults)
  77.               printf("2, ");
  78.  
  79.           int count = 1;
  80.           for (int num = 3; num <= sieveSize; num+=2)
  81.           {
  82.               if (Bits[num])
  83.               {
  84.                   if (showResults)
  85.                       printf("%d, ", num);
  86.                   count++;
  87.               }
  88.           }
  89.  
  90.           if (showResults)
  91.               printf("\n");
  92.  
  93.           printf("Passes: %d, Time: %lf, Avg: %lf, Limit: %ld, Count1: %d, Count2: %d, Valid: %d\n",
  94.                  passes,
  95.                  duration,
  96.                  duration / passes,
  97.                  sieveSize,
  98.                  count,
  99.                  countPrimes(),
  100.                  validateResults());
  101.       }
  102.  
  103.       int countPrimes()
  104.       {
  105.           int count = 1;
  106.           for (int i = 3; i < sieveSize; i+=2)
  107.               if (Bits[i])
  108.                   count++;
  109.           return count;
  110.       }
  111. };
  112.  
  113. int main()
  114. {
  115.     auto passes = 0;
  116.     auto tStart = steady_clock::now();
  117.  
  118.     while (true)
  119.     {
  120.         prime_sieve sieve(1000000L);
  121.         sieve.runSieve();
  122.         passes++;
  123.         if (duration_cast<seconds>(steady_clock::now() - tStart).count() >= 5)
  124.         {
  125.             sieve.printResults(false, duration_cast<microseconds>(steady_clock::now() - tStart).count() / 1000000, passes);
  126.             break;
  127.         }
  128.     }
  129. }
  130.  
RAW Paste Data