2016-12-27 192 views
0

我想實現Sieve of Eratosthenes算法。上述鏈接中提供的僞代碼是如何實現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. 

第一個問題是處理索引。爲簡單起見,我所做的僅僅是將索引與數據的位置進行匹配。我的下圖描述了這個問題。

enter image description here

根據上述算法,我的代碼不會產生質數。這是我實現

#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 

爲什麼我的代碼不會產生正確的答案?任何提示?

+0

在算法中最內層的循環中,步長是恆定的。你最內層的循環有一個增加的步驟。 – Mat

+0

@Mat,爲什麼它是不變的?根據這條線i^2,i^2 + i,i^2 + 2i,i^2 + 3i','i'乘以一個增加的變量。 – CroCo

+0

編譯所有警告和調試信息('g ++ -Wall -Wextra -g')。 **使用調試器**('gdb')一步一步地運行程序並查詢程序狀態。 –

回答

5

的問題是在這個循環:

 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; 
     } 

但不能混用兩種形式。

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