fork download
copy 
  1. /*
  2.  * Filename: primus.cpp
  3.  * Author:   Igor V. Krassikov
  4.  * Created:  Thu Sep 22 2016
  5.  */
  6.  
  7. // Простые числа до 2^32-1
  8.  
  9. #include <stdlib.h>
  10. #include <stdio.h>
  11. #include <string.h>
  12. #include <time.h>
  13.  
  14. constexpr inline unsigned long pow2(unsigned long i) { return 1 << i; }
  15.  
  16. unsigned long isqrt(unsigned long a)
  17. {
  18.     unsigned long x = a;
  19.     for(unsigned long z = 0; x != z; )
  20.     {
  21.         z = x;
  22.         x = (x + a/x)/2;
  23.         x = (x + a/x)/2;
  24.     }
  25.     return x;
  26. }
  27.  
  28.  
  29. constexpr unsigned long MAX_LIM = pow2(20) - 1;
  30. constexpr unsigned long ARR_LIM = (MAX_LIM >> 6) + 1;
  31. const     unsigned long SQR_LIM = isqrt(MAX_LIM);;
  32.  
  33. unsigned long primes[ARR_LIM] = { 0 }; // 0 - простое, 1 - составное
  34.  
  35. auto set_primes = [](unsigned long idx) { primes[idx >> 6] |= pow2((idx&0x0000003F)>>1); };
  36. auto get_primes = [](unsigned long idx) { return primes[idx >> 6] &  pow2((idx&0x0000003F)>>1); };
  37.  
  38. int main(int argc, const char * argv[])
  39. {
  40.     clock_t start = clock();
  41.     unsigned long Min = 2, Max = MAX_LIM;
  42.     if (argc > 1)
  43.     {
  44.         unsigned long x = strtoul(argv[1],0,0);
  45.         if (Min < x) Min = x;
  46.         if (argc > 2)
  47.         {
  48.             x = strtoul(argv[2],0,0);
  49.             if (x < Max) Max = x;
  50.         }
  51.     }
  52.     unsigned long Sqr = isqrt(Max);
  53.  
  54.     {
  55.         for(unsigned long j = 9; j <= Max; j += 3)
  56.         {
  57.             if (j%2) set_primes(j);
  58.         }
  59.         for(unsigned long i = 5; i <= Sqr; i += 6)
  60.         {
  61.             if (get_primes(i)) continue;
  62.             for(unsigned long j = i * i; j <= Max; j += i)
  63.             {
  64.                 if (j%2) set_primes(j);
  65.             }
  66.         }
  67.         for(unsigned long i = 7; i <= Sqr; i += 6)
  68.         {
  69.             if (get_primes(i)) continue;
  70.             for(unsigned long j = i * i; j <= Max; j += i)
  71.             {
  72.                 if (j%2) set_primes(j);
  73.             }
  74.         }
  75.     }
  76.     //return 0;
  77.  
  78.     int total = 0;
  79.     if (Min <= 2 && Max >= 2)
  80.     {
  81.         //puts("2");
  82.         ++total;
  83.     }
  84.     if (Min <= 2) Min = 3;
  85.     for(unsigned long i = Min; i <= Max; i+=2)
  86.     {
  87.         if (get_primes(i)) continue;
  88.         ++total;
  89.         //printf("%lu\n",i);
  90.     }
  91.     printf("%d primes in [1,2^20] for %lf ms\n",total,
  92.           double(clock()-start)*1000.0/CLOCKS_PER_SEC);
  93. }
  94.  
  95.  
Success #stdin #stdout 0s 3532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
82025 primes in [1,2^20] for 2.133000 ms
https://ideone.com/qZRLsN
language:
C++14 (gcc 8.3)
created:
7 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!