c++ - 为什么我的埃拉托色尼筛法给出了一些合数？

Question

因此，在运行我的埃拉托色尼筛法后，在某些情况下，它还给了我合数。

例如。

当数字的限制是 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++)