方法一:埃氏筛
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];
void divide(int n)
{
for(int i = 2; i <= n; i++)
{
if(!st[i])
{
primes[cnt++] = i;
for(int j = i; j <= n; j += i)
st[j] = true;
}
}
}
int main()
{
int n;
cin >> n;
divide(n);
cout << cnt << endl;
return 0;
}
方法二:线性筛法
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for(int i = 2; i <= n; i++)
{
// 存储质数
if(!st[i]) primes[cnt++] = i;
// 开始筛选
for(int j = 0; primes[j] * i <= n; j++)
{
st[i * primes[j]] = true;
if(i % primes[j] == 0) break; // 筛选过了
}
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}