为什么我的埃拉托色尼筛法会无限循环。我测试了几个数字

Question

我正在尝试通过以下伪代码在 C++ 中实现埃拉托色尼筛法算法：

Input: an integer n > 1.

Let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n: if A[i] is true: for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n: A[j] := false.

Output: all i such that A[i] is true.

但是我的代码在最后一个 for 循环中无限循环，我不知道为什么。

void primes(int n)
{
    bool numArr[n];
    for (int a=2;a<n;a++)
       {
           numArr[a]=true;
       }
    int   k,j, m = int(sqrt(n));
    for(int i=2;i<m;i++)

    {
        k=0;
        if(numArr[i]==true)
        {
            for(j=i^2;j<n;j+(k*i))
            {
                numArr[j]=false;
                k++;
            }

        }

    }

    for(int j=1;j<n;j++)
    {
        if(numArr[j]==true)
        {
            cout<<numArr[j]<<endl;
        }
    }

}

Answer 1

首先，C++ 中没有 VLA。尽管如此，一些编译器会容忍它们，而其他编译器则不会。对于便携式解决方案，std::vector 效果很好。用这个替换你的 VLA：

std::vector<bool> numArr(n);

你甚至可以把初始化放进去。不需要将所有内容都设置为 true 的循环，只需将 numArr(n) 更改为 numArr(n, true)，一切都已为您完成。

然而，您的主要问题在于：

for(j=i^2;j<n;j+(k*i))

j=i^2 并没有按照您的想法行事，并且 j+(k*i) 的增量不会增加任何东西。实际上， k 部分没有意义。改为这样做：

for (j = i*i; j < n; j += i)

你打印的 cout<<numArr[j]<<endl; 也是错误的。 numArr[j] 是一个 bool，所以每次都会打印一个 1。你肯定想打印 j 而不是 numArr[j].

虽然这不是问题，但您不必写 if (numArr[i] == true)。只需执行 if (numArr[i]) 即可。 numArr[i] 已经是 bool.

为什么我的埃拉托色尼筛法会无限循环。我测试了几个数字

Why is my sieve of Eratosthenes code looping infinitely. I have tested with a few numbers

c++

loops

sieve-of-eratosthenes