爲什麼我的Eratosthenes篩子給出了一些複合數字？

Question

因此，在運行我的Eratosthenes Sieve實現後，對於某些情況，它也給了我合成數字。

例如，

當數字的限制是10時，我也得到了2,3,5,7和9。

當限制爲30時，我會得到25以及素數。

這是爲什麼？我的代碼是：

#include <iostream> 
#include <cmath> 
#include <vector> 
using namespace std; 

long long n; 

int main() 
{ 
    cout << "Till what number to find primes of?" << endl; 
    cin >> n; 
    int m = sqrt(n); 
    vector<bool> prime(n+1, true); 
    for(int i = 2; i<m; i++) 
    { 
     if(prime[i]) 
     { 
      for(int k=i*i; k<=n; k=k+i) 
      { 
       prime[k] = false; 
      } 
     } 
    } 
    for(int j=2; j<=n; j++) 
    { 
     if(prime[j]) 
     { 
      cout << j << endl; 
     } 
    } 
    return 0; 
} 

Answer 1

因爲你檢查i < m，而不是i <= m，所以你從不檢查9的平方根，25等
變化

for(int i = 2; i<m; i++) 

到

for(int i = 2; i<=m; i++)