fork(13) download
  1. /* Run it on offline compilers like Codeblocks or Orwell/Blooodshed Dev C++
  2. * C++ Program to Implement Segmented Sieve
  3. */
  4. #include <iostream>
  5. #include <cstring>
  6. #define MAX 46656
  7. #define LMT 216
  8. #define LEN 4830
  9. #define RNG 100032
  10. #define sq(x) ((x)*(x))
  11. #define mset(x,v) memset(x, v , sizeof(x))
  12. #define chkC(x,n) (x[n >> 6] & (1 << ((n >> 1) & 31)))
  13. #define setC(x,n) (x[n >> 6] |= (1 << ((n >> 1) & 31)))
  14. using namespace std;
  15. unsigned base[MAX/64], segment[RNG/64], primes[LEN];
  16.  
  17. /*
  18. * Generates all the necessary prime numbers and marks them in base[]
  19. */
  20. void sieve()
  21. {
  22. unsigned i, j, k;
  23. for (i = 3; i < LMT; i += 2)
  24. {
  25. if (!chkC(base, i))
  26. {
  27. for (j = i * i, k = i << 1; j < MAX; j += k)
  28. setC(base, j);
  29. }
  30. }
  31. for (i = 3, j = 0; i < MAX; i += 2)
  32. {
  33. if (!chkC(base, i))
  34. primes[j++] = i;
  35. }
  36. }
  37.  
  38. /*
  39. * Returns the prime-count within range [a,b] and marks them in segment[]
  40. */
  41. int segmented_sieve(int a, int b)
  42. {
  43. unsigned i, j, k, cnt = (a <= 2 && 2 <=b )? 1 : 0;
  44. if (b < 2)
  45. return 0;
  46. if (a < 3)
  47. a = 3;
  48. if (a % 2 == 0)
  49. a++;
  50. mset (segment, 0);
  51. for (i = 0; sq(primes[i]) <= b; i++)
  52. {
  53. j = primes[i] * ((a + primes[i] - 1) / primes[i]);
  54. if (j % 2 == 0) j += primes[i];
  55. for (k = primes[i] << 1; j <= b; j += k)
  56. {
  57. if (j != primes[i])
  58. setC(segment, (j - a));
  59. }
  60. }
  61. for (i = 0; i <= b - a; i += 2)
  62. {
  63. if (!chkC(segment, i))
  64. cnt++;
  65. }
  66. return cnt;
  67. }
  68. /*
  69. * Main
  70. */
  71. int main()
  72. {
  73. sieve();
  74. int a, b;
  75. cout<<"Enter Lower Bound: ";
  76. cin>>a;
  77. cout<<"Enter Upper Bound: ";
  78. cin>>b;
  79. cout<<"Number of primes between "<<a<<" and "<<b<<": ";
  80. cout<<segmented_sieve(a, b)<<endl;
  81. return 0;
  82. }
Not running #stdin #stdout 0s 0KB
stdin
Standard input is empty
stdout
Standard output is empty