SPOJ PRIME1 Prime Generator: Wrong Answer?

Question

Doing this question on SPOJ, trying to implement a sieve and a segmented sieve to get the desired primes. My code is as follows:

//Prime Generator

#include <iostream>
#include <math.h>
#include <cstdio>

using namespace std;

int main() {
    //traditional sieve
    int squareRoot = sqrt(1000000000);
    //printf("%d\n\n", squareRoot);
    bool primeList[squareRoot] = {false}; //all primes are marked as true, composite is false

    //make entire array true
    for (int i = 1; i < squareRoot; i++){
        primeList[i] = true;
    }
    //traditional sieve to find primes first
    for (int i = 2; i <= squareRoot; i++){
        for (int j = i*i; j <= squareRoot; j+=i){
            //composites are marked as false
            primeList[j - 1] = false;
        }
    }

    //segmented sieve + output
    int a;
    scanf("%d", &a);
    while (a > 0){
        int m, n;
        scanf("%d%d", &m, &n);

        //if lower than this range, then we can just output the primes we already computed
        if (n <= squareRoot){
            for (int i = m; i <= n; i++){
                if (primeList[i - 1] == true){
                    printf("%d\n", i);
                }
            }
            printf("\n");
        }

        //it is beyond this range, so we need to segment sieve
        else {
            int upperLimit = sqrt(n); //highest we need to divide by
            int diff = n - m;
            bool myPrimes[diff + 1];

            for (int i = 0; i <= diff; i++){
                myPrimes[i] = true;
            }

            for (int i = 2; i <= upperLimit; i++){
                if (primeList[i - 1] == true){
                    int lowest = m/i * i;

                    while (lowest < m){
                        lowest += i;
                    }
                    while (lowest <= n){
                        myPrimes[lowest - m] = false;
                        lowest += i;
                    }
                }
            }
            for (int i = m; i <= n; i++){
                if (myPrimes[i - m] == true){
                    printf("%d\n", i);
                }
            }
            printf("\n");
        }
        a--;
    }
}

The basic logic I'm trying to do is:

1. First do a sieve of Eratosthenes to generate all the primes up to the sqrt of 10^9, since 10^9 is the upper limit of n.

2. If n is below sqrt(10^9), then I do not calculate anything new, just output the appropriate primes from (1).

3. If n is above sqrt(10^9), then I first calculate sqrt(n), which is the largest number we'd need, as any number bigger would not be divisible in the range [m, n].

4. Then I'd do the actual sieve, starting from 2, and trying to mark as false all numbers that are a multiple of a prime. I do 'lowest = m/i * i' to get the number that is the closest to m, where lowest <= m. If it is lower than m, then I add until it is just above m. I.E. if m==125 and n == 200, then 125/2 = 62, 62*2 = 124. 124+2 == 126, which would be the first number that is a multiple of 2 in the series [125,200].

5. Then we output any numbers that have no been marked false.

My issue is it seems my algorithm is correct (to me). I'm more than certain my first sieve works, but it seems that it might falter at generating primes larger than sqrt(10^9). However, from my testing it seems it does generate all the primes (and only primes). Is my algorithm to generate primes too uncertain? Is it a one-off issue with rounding?

My guess is that the error comes from

              for (int i = 2; i <= upperLimit; i++){
                    if (primeList[i - 1] == true){
                        int lowest = m/i * i;

                        while (lowest < m){
                            lowest += i;
                        }
                        while (lowest <= n){
                            myPrimes[lowest - m] = false;
                            lowest += i;
                        }
                    }
                }

But I can't tell where. Any tips or pointers would be welcome!

Answer 1

I got the mistake , its in the second case where you are defining myPrimes[diff] = {true} . But think of the where the time when input is like m = 1 and n > sqrt(1000000000) then it would give 1 as a prime number.

Hope that would make accept you answer.