我正在使用埃拉托色尼筛法作为素数检验。为什么我得到 2297 是复合的？

Question

我正在使用埃拉托色尼筛法计算前 500 个素数。该程序所做的是 evauate 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 对于 n == 2297 将是 48。然后，此循环将检查 n 是否可以被任何不超过 48 的素数整除，这将失败。（这个循环也应该有 i < j 作为条件，所以如果你输入一个大的 n 它不会读入垃圾）。

然后你写：

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

记住 j 当前持有素数，素数在 primes[0] 到 primes[j-1] 之间。这意味着 primes[j] 是一个垃圾值；所以你将 i 设置为导致未定义行为的垃圾。

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

我正在使用埃拉托色尼筛法作为素数检验。为什么我得到 2297 是复合的？

I'm using the sieve of Eratosthenes as a primality test. Why am I getting that 2297 is composite?

c

algorithm

primes