fork(6) download
copy 
  1. //Oryginał algorytmu znajdowania liczb pierwszych nie jest mój i jest dostępny pod adresem: https : / / github.com / abudnik / primes
  2.  
  3. #include <cstdint>
  4. #include <cstdio>
  5. #include <cmath>
  6. #include <inttypes.h>
  7. #include <iostream>
  8. #include <vector>
  9.  
  10. using namespace std;
  11.  
  12. typedef int64_t index_t;
  13.  
  14. bool isPrime(unsigned long long number){
  15.  
  16.     if(number < 2) return false;
  17.     if(number == 2) return true;
  18.     if(number % 2 == 0) return false;
  19.     for(unsigned long long i=3; (i*i)<=number; i+=2){
  20.         if(number % i == 0 ) return false;
  21.     }
  22.     return true;
  23.  
  24. }
  25.  
  26. class HashTable
  27. {
  28. public:
  29.     HashTable(size_t n)
  30.     : size(1 << (uint64_t)ceil(log2(n))),
  31.      mask(size - 1),
  32.      keys(new uint64_t[size]),
  33.      values(new uint64_t[size])
  34.     {}
  35.  
  36.     ~HashTable() {
  37.         delete[] keys;
  38.         delete[] values;
  39.     }
  40.  
  41.     void insert(uint64_t k, uint64_t v) {
  42.         size_t i = k & mask;
  43.         while (keys[i]) {
  44.             i = (i + 1) & mask;
  45.         }
  46.         keys[i] = k;
  47.         values[i] = v;
  48.     }
  49.  
  50.     index_t search(uint64_t k) const {
  51.         size_t i = k & mask;
  52.         while (keys[i]) {
  53.             if (keys[i] == k)
  54.                 return i;
  55.             else
  56.                 i = (i + 1) & mask;
  57.         }
  58.         return -1;
  59.     }
  60.  
  61.     void remove(index_t i) {
  62.         keys[i] = 0;
  63.  
  64.         for (i = (i + 1) & mask; keys[i]; i = (i + 1) & mask) {
  65.             const uint64_t key = keys[i];
  66.             keys[i] = 0;
  67.             insert(key, values[i]);
  68.         }
  69.     }
  70.  
  71.     uint64_t get_value(index_t pos) const {
  72.         return values[pos];
  73.     }
  74.  
  75. private:
  76.     const size_t size, mask;
  77.     uint64_t *keys, *values;
  78. };
  79.  
  80. vector<long long> FindPrimes()
  81. {
  82.     HashTable ht(2000);
  83.     vector<long long> primes;
  84.  
  85.     primes.push_back(2);
  86.  
  87.     for (uint64_t n = 3; n <= 4000000; n += 2) {
  88.         const index_t pos = ht.search(n);
  89.         if (pos >= 0) {
  90.             const uint64_t p = ht.get_value(pos);
  91.             ht.remove(pos);
  92.             uint64_t v = n + p + p;
  93.             for (; ht.search(v) >= 0; v += p + p);
  94.             ht.insert(v, p);
  95.         } else {
  96.             if (n <= 2000) {
  97.                 ht.insert(n * n, n);
  98.             }
  99.             primes.push_back(n);
  100.         }
  101.     }
  102.     return primes;
  103. }
  104.  
  105. int main()
  106. {
  107.  
  108.     vector<long long> miniPrimes = FindPrimes();
  109.     ios_base::sync_with_stdio(false);
  110.     cin.tie(NULL);
  111.     int t;
  112.     long long start, stop,i,range;
  113.     cin >> t;
  114.     while(t--) {
  115.         cin >> start >> stop;
  116.         range = stop-start+1;
  117.  
  118.         if(stop-start<500) {
  119.             int ile = 0;
  120.             int maxi = 0;
  121.             for(int i = start; i <=stop; i++) {
  122.                 if(!isPrime(i)) {
  123.                     ile++;
  124.                 } else {
  125.                     if(ile>maxi) maxi = ile;
  126.                     ile = 0;
  127.                 }
  128.             }
  129.             if (ile>maxi) maxi = ile;
  130.             cout << maxi << '\n';
  131.         } else {
  132.  
  133.             vector<long long> primes(range);
  134.  
  135.             int maxi = 0;
  136.             if(start == 0) {
  137.                 if(stop == 0) maxi = 1;
  138.                 if(stop >= 1) maxi = 2;
  139.             } else if(start == 1) {
  140.                 if(stop >= 1) maxi = 1;
  141.             }
  142.             int ostatnia = 0;
  143.  
  144.             for(long long prime : miniPrimes) {
  145.                 if(prime > stop) break;
  146.                 if(prime>=start)
  147.                     if(ostatnia == 0) {
  148.                         ostatnia = prime;
  149.                     } else {
  150.                         if(prime-ostatnia-1 > maxi) maxi = prime-ostatnia-1;
  151.                         ostatnia = prime;
  152.                     }
  153.             }
  154.             if (ostatnia == 0) maxi = stop-start+1;
  155.             else {
  156.                 if(stop-ostatnia>maxi) maxi = stop-ostatnia;
  157.             }
  158.             if (stop-ostatnia-start+1>maxi) maxi = stop-ostatnia-start+1;
  159.             cout << maxi << '\n';
  160.  
  161.         }
  162.  
  163.     }
  164.     return 0;
  165. }
Success #stdin #stdout 0.14s 64128KB
comments (?)
stdin
copy 
101
0 4000000
3 3
3 5
7 11
100 4000
300 5000
4000000 4000000
3000000 4000000
1234567 2345678
123 876
11 111
0 0
1 3
1 10
10 10000
20 22
1223 2731
1222 2731
1222 2732
1222 2730
9677 9679
7907 15359
100 101377
0 101377
333 3990762
3990761 3999999
55 5555
333 444
3982399 3999997
350803 3982399
2866143 3782576
1691344 3025671
1130380 1588454
1666082 1952582
1788690 3233070
1943098 3001690
670420 3665322
1439853 3502769
484853 3302803
18323 1648119
2965079 3012592
971722 2813108
1431286 3863346
3443807 3910014
2405979 2472514
2113940 3577769
1135696 3118527
1118879 3308197
160916 2297109
1089436 1834529
1840594 3450793
2280440 3313663
798700 2551985
2853524 3537720
2908373 3280664
3245766 3473002
1314975 2593092
3962739 3996149
3619350 3704271
1614885 3876321
3230818 3619452
529655 3444127
3014260 3087023
2325498 2518978
466342 1028933
2808192 3626230
2385598 2511563
350783 1673508
1033382 3277507
3776772 3974738
1205866 3950861
2936839 3007984
2386057 3889899
3135049 3917117
3753634 3998778
1400060 3957561
1634173 3153618
1274261 3056831
194913 2104766
1062583 1257647
3514163 3757507
3763153 3781186
399349 2208353
2312720 2807885
2319466 2889721
1676571 3324864
854769 2662090
1760426 3071702
2211392 3101643
890290 2074874
1698654 1923046
307157 2441433
3639492 3924134
1479332 2377972
3985140 3991917
3630600 3716484
2077493 2617708
592800 2791785
3233158 3688114
48291 579080
15 151515
stdout
copy 
147
0
1
3
33
33
1
137
147
17
7
1
1
3
35
3
33
33
33
33
1
35
71
71
147
89
33
9
89
147
121
147
131
125
147
147
147
147
147
131
87
147
147
137
89
121
147
147
147
131
147
121
147
121
121
109
147
81
91
147
111
147
109
99
113
121
93
131
147
137
147
87
137
137
137
147
147
147
147
105
111
95
147
111
111
147
147
147
119
147
125
147
137
147
61
91
109
147
111
113
71
https://ideone.com/540Gkz
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!