我想實現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.
第一個問題是處理索引。爲簡單起見,我所做的僅僅是將索引與數據的位置進行匹配。我的下圖描述了這個問題。
根據上述算法,我的代碼不會產生質數。這是我實現
#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
爲什麼我的代碼不會產生正確的答案?任何提示?
在算法中最內層的循環中,步長是恆定的。你最內層的循環有一個增加的步驟。 – Mat
@Mat,爲什麼它是不變的?根據這條線i^2,i^2 + i,i^2 + 2i,i^2 + 3i','i'乘以一個增加的變量。 – CroCo
編譯所有警告和調試信息('g ++ -Wall -Wextra -g')。 **使用調試器**('gdb')一步一步地運行程序並查詢程序狀態。 –