SPOJ PRIME1 Prime Generator：错误答案？

在SPOJ上做this question，尝试使用筛子和分段筛子来获得所需的质数 . 我的代码如下：

//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--;
    }
}

我想要做的基本逻辑是：

• 首先筛选Eratosthenes以生成直至10 ^ 9的sqrt的所有素数，因为10 ^ 9是n的上限 .

• 如果n低于sqrt（10 ^ 9），那么我不计算任何新的，只输出（1）中的相应素数 .

• 如果n高于sqrt（10 ^ 9），那么我首先计算sqrt（n），这是我们需要的最大数，因为任何更大的数字在[m，n]范围内都不可分 .

• 然后我会从2开始做实际的筛子，并试图将所有数字标记为假，这是一个素数的倍数 . 我做'最低= m / i * i'得到最接近m的数字，其中最低<= m . 如果它低于m，那么我添加直到它高于m . I.E.如果m == 125且n == 200，则125/2 = 62,62 * 2 = 124. 124 2 == 126，这将是系列[125,200]中第一个为2的倍数的数字 .

• 然后我们输出任何没有标记为false的数字 .

我的问题是我的算法似乎是正确的（对我来说） . 我不仅仅确定我的第一个筛子有效，但似乎在生成大于sqrt（10 ^ 9）的质数时可能会步履蹒跚 . 但是，从我的测试来看，它似乎确实产生了所有素数（并且只有素数） . 我的算法生成素数太不确定了吗？四舍五入是一次性的问题吗？

我的猜测是错误来自

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

但我不知道在哪里 . 欢迎任何提示或指示！