Prime number generator doesn't work for small numbers

Question

Since 2 days I'm struggling with PRIME1 problem from SPOJ. 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). I'm using Segmented Sieve of Eratosthenes. SPOJ link

Here's the problem:

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

And my code:

#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;

    bool sieve[n];
    memset(sieve, true, sizeof(sieve));

    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 it varies, depending on the input.

`bool sieve[n]` is not a valid `C++`. It's a [Variable Length Array (VLA)](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard), which are but an extensions to some compilers. I see you are already using `std::vector`. You should also use it for `sieve`. — Fureeish, Dec 09 '18 at 22:49
I've been using it before, but due to some implementation problems I replaced `std::vector` with bool array. Though now with vector it works fine so I've changed it. Thanks! — Kacper Paluch, Dec 09 '18 at 23:22
The first call to simpleSieve does the job basically. Maybe the problem is in the calculation of `range` . — Damien, Dec 09 '18 at 23:29

feature sky · Answer 1 · 2018-12-11T08:50:47.710

2

First print the prime numbers greater than left, which were generated using the simpleSieve.
Also, 1 is not a prime number, so we will skip it while printing other primes:

for (int i = 0; i<primes.size(); i++) {
    if (primes[i] >= left)
        cout << primes[i] << "\n";
}

for(int i=left; i<=right; i++){
    if (i == 1){
        continue;
    }
    if(sieve[i - left])   cout << i << "\n";
}
cout << "\n";  //empty line before next testcase starts

edited Dec 11 '18 at 08:50

answered Dec 10 '18 at 02:29

feature sky

171
4
15

See input _3 5_ or _149 170_. This fix helped a bit for the beginning part for bigger ranges that start from 1 but `+primes[i]` cause it to avoid crucial sieving part (i guess). I think the problem might be somewhere in saving already sieved numbers to vector (output _4_ from the _3 5_ input suggests it). – Kacper Paluch Dec 10 '18 at 07:25
After night I came back to this problem and noticed what exactly is the problem after applying your fix. The output always display 2 consecutive numbers starting from `right` (obviously, these are being set to be true). Still don't know how to fix that. – Kacper Paluch Dec 10 '18 at 20:57
@KacperPaluch I have modified the code and this should definitely work. Your code was perfect. All I did is, printing the primes generated by simpleSieve if they are in given range. – feature sky Dec 11 '18 at 08:53

Prime number generator doesn't work for small numbers

1 Answers1