改良后的埃氏筛法 O(loglogn)
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 10000010;
int n;
bool st[N];
int primes[N], cnt;
signed main(void)
{
cin >> n;
for (int i = 2; i <= n; i++)
{
if (st[i])
{
continue;
}
primes[cnt++] = i;
for (int j = i * i; j <= n; j += i)
{
st[j] = true;
}
}
cout << cnt << endl;
return 0;
}
欧拉筛法 O(n)
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 10000010;
int n;
bool st[N];
int primes[N], cnt;
signed main(void)
{
cin >> n;
for (int i = 2; i <= n; i++)
{
if (!st[i])
{
primes[cnt++] = i;
}
for (int j = 0; i * primes[j] <= n; j++)
{
st[i * primes[j]] = true;
if (i % primes[j] == 0)
{
break;
}
}
}
cout << cnt << endl;
return 0;
}