为什么我的埃拉托斯特尼代码筛无限循环。我用几个数字测试过

Question

我试图在C中实现埃拉托斯特尼的筛子算法，从下面的伪代码中：

输入：整数n

设A是一个布尔值数组，索引为整数2到n，最初都设置为真。

对于 i = 2， 3， 4， ...， 不超过 √n： 如果 A[i] 为真：对于 j = i2， i2 i， i2 2i， i2 3i， ...， 不超过 n： A[j] ：= 假。

输出：所有 i 使得 A[i] 为真。

然而，我的代码在最后一个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)

您的< code>cout打印

虽然这不是问题，但你不必写如果（numArr[i] == true）。只需执行如果 （数字 [i]） 代替。数字[i]已经是一个布尔。