エラトステネスアルゴリズムのふるいを実装する方法

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乗数でiでjをインクリメントする必要があり、次のいずれか

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

やブランドの新しいを計算の値

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

ではなく、二つのアプローチをミックス：aをインクリメントして。

Answer 2

forループの内側が大きすぎます。正しい解決策は、ステップ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