fork download
copy 
  1. #include <iostream>
  2. #include <list>         // from stackoverflow.com/q/55022028/849891
  3. #include <cmath>       //      by stackoverflow.com/users/9434763/apoorva-raju
  4. #include <ctime>      // tweaked by stackoverflow.com/users/849891/will-ness
  5. using namespace std;    
  6. /*  
  7. check_prime__list:
  8.  
  9.           time taken       No of divisions         No of primes
  10. 10M:    0.873 seconds        286144936                664579
  11. 20M:    2.169 seconds        721544444               1270607
  12.                  (2.5x)          (2.5x)    (log 2.5 / log 2 = 1.32)
  13.                                        (2B: over 2.169*100**1.32/60 = 16 minutes)
  14. check_prime__nums:
  15.  
  16.           time taken       No of divisions         No of primes
  17. 10M:    4.650 seconds       1746210131                664579
  18. 20M:   12.585 seconds       4677014576               1270607
  19.                  (2.7x)          (2.7x)    (log 2.7 / log 2 = 1.43)
  20.                                        (2B: over 12.585*100**1.43/3600 = 2.5 hours)
  21. */
  22.  
  23. list<long long> primeno;
  24. long int noofdiv = 0;      /// LONG!!!! was wrapping-around with INT, #@%$&$#
  25. void ListPrimeNumber();
  26. int no_primes = 3;
  27.  
  28. int main()
  29. {
  30.     clock_t time_req = clock();
  31.     ListPrimeNumber();
  32.     time_req = clock() - time_req;
  33.     cout << "\ntime taken " << static_cast<float>(time_req) / CLOCKS_PER_SEC << " seconds";
  34.     cout << "\nNo of divisions : " << noofdiv;
  35.     cout << "\nNo of primes : " << no_primes;
  36.     return 0;
  37. }
  38.  
  39. void check_prime(int i);
  40.  
  41. void ListPrimeNumber()
  42. {
  43.     primeno.push_back(2);
  44.     primeno.push_back(3);
  45.     primeno.push_back(5);
  46.     for (long long i = 6; i <= 10000000; i++)
  47.     {
  48.         check_prime(i);
  49.     }
  50.  
  51. }
  52.  
  53. void check_prime(int i)   // __list
  54. {
  55.     try
  56.     {
  57.         int limit = sqrt(i);
  58.         for (int iter : primeno)
  59.         {
  60.             if (iter > limit)
  61.             {
  62.                 primeno.push_back(i);
  63.                 ++no_primes;
  64.                 break;
  65.             }
  66.             else if ( (++noofdiv , (i % iter) == 0) )
  67.             {
  68.                 break;
  69.             }
  70.         }
  71.     }
  72.  
  73.     catch (exception ex)
  74.     {
  75.         std::cout << "Message";
  76.     }
  77. }
  78.  
  79. void check_prime__nums(int i)
  80. {
  81.     try
  82.     {
  83.         int j = 0;
  84.         int limit = sqrt(i);
  85.         for (j = 2 ; j <= limit;j++)
  86.         {
  87.             if(  (++noofdiv , (i % j) == 0) )
  88.             {
  89.                 break;
  90.             }
  91.         }
  92.         if( j > limit)
  93.         {
  94.             primeno.push_back(i);
  95.             ++no_primes;
  96.         }
  97.     }
  98.  
  99.     catch (exception ex)
  100.     {
  101.         std::cout << "Message";
  102.     }
  103. }
Success #stdin #stdout 0.9s 35960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
time taken 0.901626 seconds
No of divisions : 286144936
No of primes : 664579
https://ideone.com/VPOnux
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!