Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define ll long long
- #define M 1000000
- #define on(x) (marked[x / 64] & (1 << ((x % 64) / 2)))
- #define mark(x) (marked[x / 64] |= (1 << ((x % 64) / 2)))
- using namespace std;
- int marked[M / 64 + 1];
- vector<int>primes;
- void sieve()
- {
- for(int i = 3; i * i <= M; i += 2)
- {
- if(!on(i))
- {
- for(int j = i * i; j <= M; j += i + i)
- mark(j);
- }
- }
- primes.push_back(2);
- for(int i = 3; i <= M; i += 2)
- {
- if(!on(i))
- primes.push_back(i);
- }
- }
- vector<int> segsieve(int l, int r)
- {
- vector<int>range_prime;
- bool is_prime[r - l + 1];
- for(int i = 0; i < r - l + 1; i++)
- is_prime[i] = true;
- if(l == 1)
- is_prime[0] = false;
- for(int i = 0; primes[i] * primes[i] <= r; i++)
- {
- int current_prime = primes[i];
- int base = (l / current_prime) * current_prime;
- if(base < l)
- base += current_prime;
- for(int j = base; j <= r; j += current_prime)
- is_prime[j - l] = false;
- if(base == current_prime)
- is_prime[base - l] = true;
- }
- for(int i = 0; i < r - l + 1; i++)
- {
- if(is_prime[i] == true)
- range_prime.push_back(i+l);
- }
- return range_prime;
- }
- int main()
- {
- sieve();
- int l, u;
- while(cin >> l >> u)
- {
- vector<int>primes_in_range;
- primes_in_range = segsieve(l, u);
- int diff1 = INT_MIN, diff2 = INT_MAX;
- if(primes_in_range.size() <= 1)
- cout << "There are no adjacent primes." << endl;
- else
- {
- int a, b, c, d;
- for(int i = 1; i < primes_in_range.size(); i++)
- {
- if(primes_in_range[i] - primes_in_range[i -1] < diff2)
- {
- b = primes_in_range[i];
- a = primes_in_range[i - 1];
- diff2 = primes_in_range[i] - primes_in_range[i - 1];
- }
- if(primes_in_range[i] - primes_in_range[i -1] > diff1)
- {
- d = primes_in_range[i];
- c = primes_in_range[i - 1];
- diff1 = primes_in_range[i] - primes_in_range[i - 1];
- }
- }
- printf("%d,%d are closest, %d,%d are most distant.\n", a, b, c, d);
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment