c++ - Eratosthenes算法的筛法如何实现

Question

我想实现 Sieve of Eratosthenes算法。前面链接中提供的伪代码是

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 = i^2, i^2+i, i^2+2i, i^2+3i, ..., not exceeding n :
      A[j] := false

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

第一个问题是处理索引。为了简单起见，我所做的只是将索引与数据位置相匹配。我的下图描述了这个问题。

我的代码没有根据上述算法生成素数。这是我的实现

#include <iostream>
#include <vector>
#include <cmath>


int main()
{
    int n(30);
    std::vector<bool> A;

    for( int i(2); i <= n+2; ++i )
        A.push_back(true);

    for ( int i(2); i <= sqrt(n); ++i ){
        if ( A[i] == true ){
            int a(0);
            for (  int j(i*i); j <= n; j += a*i ){
                A[j] = false;
                ++a;
            }
        }
    }
    for ( int i(2); i < A.size(); ++i ){
        if ( A[i] == true )
            std::cout << i  << " ";
    } 
    std::cout << std::endl;

    return 0;
}

结果是

2 3 5 7 8 11 13 14 15 17 19 20 21 22 23 26 28 29

为什么我的代码没有产生正确的答案？有什么提示吗？

Answer 1

问题出在这个循环中:

        for (  int j(i*i); j <= n; j += a*i ){
            A[j] = false;
            ++a;
        }

你应该将 j 增加 i 而没有 a 乘数:

        for (  int j(i*i); j <= n; j += i ){
            A[j] = false;
        }

或者用递增的a计算j的新值:

        for (  int a(0), j(i*i); j <= n; j = i*i + ++a*i ){
            A[j] = false;
        }

但不要混合使用这两种方法。