SHARE
TWEET

Untitled

a guest Feb 18th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. std::vector<unsigned int> prs;
  6. std::vector<unsigned long long> prSum;
  7.  
  8. unsigned long long mulmod(unsigned long long a, unsigned long long b, unsigned long long mdlo) {
  9.     if (a <= 0xFFFFFFF && b <= 0xFFFFFFF) {
  10.         return (a * b) % mdlo;
  11.     }
  12.     unsigned long long result = 0;
  13.     unsigned long long factor = a % mdlo;
  14.     while (b > 0) {
  15.         if (b & 1) {
  16.             result += factor;
  17.             if (result >= mdlo) {
  18.                 result %= mdlo;
  19.             }
  20.         }
  21.         factor <<= 1;
  22.         if (factor >= mdlo) {
  23.             factor %= mdlo;
  24.         }
  25.         b >>= 1;
  26.     }
  27.     return result;
  28. }
  29.  
  30. unsigned long long powmod(unsigned long long base, unsigned long long expo, unsigned long long mdlo) {
  31.     unsigned long long result = 1;
  32.     while (expo > 0) {
  33.         if (expo & 1) {
  34.             result = mulmod(result, base, mdlo);
  35.         }
  36.         base = mulmod(base, base, mdlo);
  37.         expo >>= 1;
  38.     }
  39.     return result;
  40. }
  41.  
  42. bool isPrime(unsigned long long p) {
  43.     const unsigned int biPri = (1 << 2) | (1 << 3) | (1 << 5) | (1 << 7) | (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19) | (1 << 23) | (1 << 29);
  44.     if(p < 31) {
  45.         return (biPri & (1 << p)) != 0;
  46.     }
  47.     if(p % 2 == 0 || p % 3 == 0 || p % 5 == 0 || p % 7 == 0 || p % 11 == 0 || p % 13 == 0 || p % 17 == 0) {
  48.         return false;
  49.     }
  50.     if(p < 17 * 19) {
  51.         return true;
  52.     }
  53.     const unsigned int tesAg1[] = {377687, 0};
  54.     const unsigned int tesAg2[] = {31, 73, 0};
  55.     const unsigned int tesAg3[] = {2, 7, 61, 0};
  56.     const unsigned int tesAg4[] = {2, 13, 23, 1662803, 0};
  57.     const unsigned int tesAg7[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022, 0};
  58.     const unsigned int* tesAgst = tesAg7;
  59.    
  60.     if (p < 5329) {
  61.         tesAgst = tesAg1;
  62.     } else if(p < 9080191) {
  63.         tesAgst = tesAg2;
  64.     } else if(p < 4759123141ULL) {
  65.         tesAgst = tesAg3;
  66.     } else if(p < 1122004669633ULL) {
  67.         tesAgst = tesAg4;
  68.     }
  69.  
  70.     auto d = p - 1;
  71.     d >>= 1;
  72.     unsigned int shift = 0;
  73.     while ((d & 1) == 0) {
  74.         shift++;
  75.         d >>= 1;
  76.     }
  77.     do {
  78.         auto x = powmod(*tesAgst++, d, p);
  79.         if (x == 1 || x == (p - 1)) {
  80.             continue;
  81.         }
  82.         bool mPrime = false;
  83.         for(unsigned int r = 0; r < shift; r++) {
  84.             x = powmod(x, 2, p);
  85.             if(x == 1) {
  86.                 return false;
  87.             }
  88.             if(x == (p - 1)) {
  89.                 mPrime = true;
  90.                 break;
  91.             }
  92.         }
  93.         if(!mPrime) {
  94.             return false;
  95.         }
  96.     } while(*tesAgst != 0);
  97.     return true;
  98. }
  99.  
  100. void morePrimes(unsigned int num) {
  101.     if (prs.empty()) {
  102.         prs.reserve(4 * std::pow(10, 5));
  103.         prSum.reserve(4 * std::pow(10, 5));
  104.         prs.push_back(2);
  105.         prs.push_back(3);
  106.         prSum.push_back(2);
  107.     }
  108.     for (auto i = prs.back() + 2; prs.size() <= num; i += 2) {
  109.         bool isPrime = true;
  110.         for (auto x : prs) {
  111.             if ((x * x) > i) {
  112.                 break;
  113.             }
  114.             if ((i % x) == 0) {
  115.                 isPrime = false;
  116.                 break;
  117.             }
  118.         }
  119.         if (isPrime) {
  120.             prs.push_back(i);
  121.         }
  122.     }
  123.     for (auto i = prSum.size(); i < prs.size(); i++) {
  124.         prSum.push_back(prSum.back() + prs[i]);
  125.     }
  126. }
  127.  
  128. int main() {
  129.     const unsigned int ppb = std::pow(10, 4);
  130.     morePrimes(ppb);
  131.     unsigned int T;
  132.     std::cin >> T;
  133.     while (T--) {
  134.         unsigned long long N = std::pow(10, 6);
  135.         std::cin >> N;
  136.         unsigned long long best = 2;
  137.         unsigned int maxLength = 0;
  138.         unsigned int start = 0;
  139.         while (prs[start] <= 131 && prs[start] <= N) {
  140.             unsigned long long subtract = 0;
  141.             if (start > 0) {
  142.                 subtract = prSum[start - 1];
  143.             }
  144.             unsigned int pos = start + maxLength;
  145.             while (prSum[pos] - subtract <= N) {
  146.                 pos++;
  147.                 if (pos + 100 >= prs.size()) {
  148.                     morePrimes(prs.size() + ppb);
  149.                 }
  150.             }
  151.             pos--;
  152.             while ((pos - start) > maxLength) {
  153.                 unsigned long long sum = prSum[pos] - subtract;
  154.                 if (isPrime(sum)) {
  155.                     maxLength = pos - start;
  156.                     best = sum;
  157.                     break;
  158.                 }
  159.                 pos--;
  160.             }
  161.             start++;
  162.         }
  163.         if (best >= 2) {
  164.             maxLength++;
  165.         }
  166.         std::cout << best << " " << maxLength << std::endl;
  167.     }
  168.     return 0;
  169. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top