c - 我使用埃拉托色尼筛作为素性测试。为什么我得到 2297 是复合数？

Question

我正在使用埃拉托斯特尼筛法来计算前 500 个素数。该程序的作用是评估 n % p，其中 n 是用户输入，p 介于 2 和 sqrt(n) 之间。

我正在针对 n = 2297 的情况测试我的程序，该情况是素数。为什么我的程序说它是复合的？

bool primalityTestSieve(int n){
    if(n == 2) return true; //tiny complication due to ceil(sqrt(2))

    //Sieve with first MAX
    bool arr[MAX - 1];
    int i, j, s = ceil(sqrt(n));
    for(i = 2; i < MAX; i++){
        arr[i - 2] = true;          //fill arr[] with true
    }
    for(i = 2; i < (int) sqrt(MAX); i++){
        if(arr[i - 2]){
            for(j = i*i; j < MAX; j+= i)
                arr[j - 2] = false;
        }
    }

    //Array storing the primes
    int primes[MAX];
    j = 0;  //Counter for the index of the primes
    for(i = 0; i < MAX; i++)
        if(arr[i]){
            primes[j] = i + 2;
            j++;
        }

    //Prime test, first using sieve
    for(i = 0; primes[i] <= s; i++)
        if(n % primes[i] == 0) return false;

    //Naive prime test for larger divisors
    for (i = primes[j]; i <= s/2; i++)
            if(((n % 2) == 0)||((n % (2*i + 1)) == 0))  return false;
    return true;
}

请注意，MAX 是一个参数化宏，等于 500。

Answer 1

您的代码使用筛子来查找 2 之间的素数和500 。 (不是你在文中所说的前 500 个素数)。

然后将这些素数复制到 primes[] 中数组 j作为数组中有多少项的计数。那么此时primes[]包含一些小于 500 的数字接下来是一堆垃圾。

然后你就有了代码:

for(i = 0; primes[i] <= s; i++)

s将是48对于 n == 2297 。然后，该循环将检查 n可被 48 以内的任何素数整除，这会失败。 (这个循环还应该有 i < j 作为条件，这样如果您输入一个大的 n ，它就不会读入垃圾。)。

但是你可以这样写:

for (i = primes[j]; i <= s/2; i++)

记住j当前保存素数计数，素数位于 primes[0] 中通过primes[j-1] 。这意味着primes[j]是垃圾值；所以你设置i导致未定义行为的垃圾。

(我不确定你在最后一个循环中实际上想要做什么，不清楚你想从哪里开始和结束，或者为什么你测试 n%2 每个循环迭代等 - 如果你可以描述什么你试图在那里做，然后我会建议一些代码)。