Итак, после запуска моей реализации Решета Эратосфена, в некоторых случаях он также дает мне составные числа.
Например.
Когда предел чисел равен 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;
}
Потому что вы проверяете i < m
скорее, чем i <= m
так что вы никогда не проверяете квадратный корень из 9, из 25 и т. д.
+ Изменить
for(int i = 2; i<m; i++)
в
for(int i = 2; i<=m; i++)
Других решений пока нет …