如何实现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; 
     } 

您应该没有a乘数递增j通过i：

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

或计算新品牌值为j与递增a：

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

但不能混用两种形式。

Answer 2

内部for-loop步骤太大。正确的解决方案是使步骤j += i，变量a不需要。

#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){ 
      for ( int j(i*i); j <= n; j += i){ 
       A[j] = false; 
      } 
     } 
    } 
    for (int i(2); i < A.size(); ++i){ 
     if (A[i] == true) 
      std::cout << i << " "; 
    } 
    std::cout << std::endl; 

    return 0; 
} 

Live Demo