c++ - 为什么我的Eratosthenes代码筛网无限循环。我已经测试了一些数字

我正在尝试通过以下伪代码在C ++中实现Eratosthenes算法的筛网：


  输入：n> 1的整数。
  
  假设A为布尔值数组，由2到n的整数索引，
  最初所有设置为true。
  
  对于i = 2，3，4，...，不超过√n：
  如果A [i]为true：
   对于j = i2，i2 + i，i2 + 2i，i2 + 3i，...，不超过n：
    A [j]：=假。
  
  输出：所有使A [i]为真的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;
        }
    }

}

最佳答案

首先，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。