fork(3) download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <math.h>
  4. #include <bitset>
  5.  
  6. using namespace std;
  7.  
  8. bitset<50003> A;
  9. unsigned int P[3401];
  10. char buffer[8192];
  11. int ind = 0;
  12.  
  13. inline void flush()
  14. {
  15. fputs(buffer,stdout);
  16. ind = 0;
  17. }
  18.  
  19. static char sbuf[12] = {0,0,0,0,0,0,0,0,0,0,'\n',0};
  20. inline char * itoa(unsigned int _a, unsigned int & _len)
  21. {
  22. char *pos = sbuf + 10;
  23. do
  24. {
  25. *--pos = '0' + (_a%10);
  26. _a/=10;
  27. } while(_a);
  28. _len = sbuf+11-pos;
  29. return pos;
  30. }
  31.  
  32. inline void bufwrite(unsigned int _a)
  33. {
  34. char *s = 0;
  35. unsigned int len;
  36.  
  37. s = itoa(_a, len);
  38. strcpy(buffer+ind, s);
  39. ind+=len;
  40.  
  41. if(ind>8000)
  42. flush();
  43. }
  44.  
  45. inline bool print_from_array(unsigned int _m, unsigned int _n)
  46. {
  47. if(_m > 31607) return true;
  48. if(_n < 2) return false;
  49. if(_m <= 2) {bufwrite(2); _m=2;}
  50. if(_n > 2)
  51. {
  52. unsigned int i = 0;
  53. for(i = 0; i < 3400; i++)
  54. {
  55. if((P[i] >= _m) && (P[i] <= _n))
  56. bufwrite(P[i]);
  57. else if(P[i] >= _n) return false;
  58. }
  59. }
  60. else
  61. return false;
  62. return true;
  63. }
  64.  
  65. void precalc()
  66. {
  67. unsigned int pp = 3, i = 0, j;
  68. for(; pp <= 178; pp+=2, i++)
  69. if(!A[i])
  70. for(j = i+pp; j <= 15802; j+=pp)
  71. A[j] = true; // not a prime
  72.  
  73. for(i = 0, j = 0; i <= 15802; i++)
  74. if(!A[i]) P[j++] = (i<<1) + 3;
  75. P[3400] = 100000;
  76. A.reset();
  77. }
  78.  
  79. void print_primes(unsigned int _m, unsigned int _n)
  80. {
  81. if(!print_from_array(_m, _n)) {flush();return;}
  82.  
  83. if(_m<=31607) _m = 31627;
  84. unsigned int max = (unsigned int) sqrt((double)_n) +1, c, p=3, i=0, j, k;
  85. for(; max >= P[i]; p = P[++i])
  86. {
  87. c = (unsigned int) ceil((double)_m/p)*p;
  88. if(!(c&1)) c+=p;
  89. for(j = c, k = (c-_m)/2; j <= _n; j += 2*p, k += p)
  90. A[k] = true;
  91. }
  92.  
  93. p = _m&1 ? _m : _m+1;
  94. for(i = 0; p <= _n; p+=2, i++)
  95. if(!A[i]) bufwrite(p);
  96. flush();
  97.  
  98. A.reset();
  99. }
  100.  
  101. int main()
  102. {
  103. unsigned int t=0, m=0, n=0;
  104. scanf("%u", &t);
  105.  
  106. precalc();
  107. while(t--)
  108. {
  109. scanf("%u %u", &m, &n);
  110. print_primes(m, n);
  111. puts("");
  112. }
  113.  
  114. return 0;
  115. }
Success #stdin #stdout 0s 2712KB
comments (?)
stdin
copy 
2
1 10
3 5
stdout
copy 
2
3
5
7

3
5
https://ideone.com/aK7SLQ
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!