Salman_CUET_18

Distance prime

Sep 17th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.38 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define M 1000000
  4. #define on(x) (marked[x / 64] & (1 << ((x % 64) / 2)))
  5. #define mark(x) (marked[x / 64] |= (1 << ((x % 64) / 2)))
  6. using namespace std;
  7. int marked[M / 64 + 1];
  8. vector<int>primes;
  9. void sieve()
  10. {
  11.     for(int i = 3; i * i <= M; i += 2)
  12.     {
  13.         if(!on(i))
  14.         {
  15.             for(int j = i * i; j <= M; j += i + i)
  16.                 mark(j);
  17.         }
  18.     }
  19.     primes.push_back(2);
  20.     for(int i = 3; i <= M; i += 2)
  21.     {
  22.         if(!on(i))
  23.             primes.push_back(i);
  24.     }
  25. }
  26. vector<int> segsieve(int l, int r)
  27. {
  28.     vector<int>range_prime;
  29.     bool is_prime[r - l + 1];
  30.     for(int i = 0; i < r - l + 1; i++)
  31.         is_prime[i] = true;
  32.     if(l == 1)
  33.         is_prime[0] = false;
  34.     for(int i = 0; primes[i] * primes[i] <= r; i++)
  35.     {
  36.         int current_prime = primes[i];
  37.         int base = (l / current_prime) * current_prime;
  38.         if(base < l)
  39.             base += current_prime;
  40.         for(int j = base; j <= r; j += current_prime)
  41.             is_prime[j - l] = false;
  42.         if(base == current_prime)
  43.             is_prime[base - l] = true;
  44.     }
  45.     for(int i = 0; i < r - l + 1; i++)
  46.     {
  47.         if(is_prime[i] == true)
  48.             range_prime.push_back(i+l);
  49.     }
  50.     return range_prime;
  51. }
  52. int main()
  53. {
  54.     sieve();
  55.     int l, u;
  56.     while(cin >> l >> u)
  57.     {
  58.         vector<int>primes_in_range;
  59.         primes_in_range = segsieve(l, u);
  60.  
  61.        int diff1 = INT_MIN, diff2 = INT_MAX;
  62.        if(primes_in_range.size() <= 1)
  63.             cout << "There are no adjacent primes." << endl;
  64.        else
  65.        {
  66.            int a, b, c, d;
  67.            for(int i = 1; i < primes_in_range.size(); i++)
  68.            {
  69.                if(primes_in_range[i] - primes_in_range[i -1] < diff2)
  70.                {
  71.                    b = primes_in_range[i];
  72.                    a = primes_in_range[i - 1];
  73.                    diff2 = primes_in_range[i] - primes_in_range[i - 1];
  74.                }
  75.                if(primes_in_range[i] - primes_in_range[i -1] > diff1)
  76.                {
  77.                    d = primes_in_range[i];
  78.                    c = primes_in_range[i - 1];
  79.                    diff1 = primes_in_range[i] - primes_in_range[i - 1];
  80.                }
  81.            }
  82.            printf("%d,%d are closest, %d,%d are most distant.\n", a, b, c, d);
  83.        }
  84.     }
  85.     return 0;
  86. }
Add Comment
Please, Sign In to add comment