Since 2 days I’m struggling with PRIME1 problem. I managed to write a program that works fine for large numbers, but I can’t figure out why does it display such messed numbers in the beginning range (usually 1-11), e.g. for input “1 10” the output is “1 5 7” and for “1 100” the first number of the output is 1 and the next one is 13… The rest is OK though. I’m using Segmented Sieve of Eratosthenes.
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000000
#define MAX_SQRT sqrt(MAX)
vector<bool> is_prime(MAX_SQRT, true);
void simpleSieve(int limit, vector<int>& primes)
{
for(int p=2; p*p<=limit; p++) {
if(is_prime[p] == true) {
for(int i=p*p; i<=limit; i+=p)
is_prime[i] = false;
}
}
for(int i=2; i<=limit; i++) {
if(is_prime[i]) primes.push_back(i);
}
}
void segmentedSieve(int left, int right)
{
int range = floor(sqrt(right)) + 1;
vector<int> primes;
simpleSieve(range, primes);
int n = right - left + 1;
vector<bool> sieve(n, true);
for (int i = 0; i<primes.size(); i++) {
int low = floor(left/primes[i]) * primes[i];
if(low < left)
low += primes[i];
for(int a=low; a<=right; a+=primes[i]) {
sieve[a - left] = false;
}
}
for(int i=left; i<=right; i++)
if(sieve[i - left]) cout << i << "\n";
}
int main()
{
int t;
cin >> t;
while(t--) {
int left, right;
cin >> left >> right;
segmentedSieve(left, right);
}
return 0;
}
I’ve tried hardcoding the beginning part, but as I mentioned, it varies depending on the input.