题目描述
求 \(1,2,\cdots,N\) 中素数的个数。
输入格式
一行一个整数 \(N\)。
输出格式
一行一个整数，表示素数的个数。
样例 #1
样例输入 #1
10
样例输出 #1
4
提示
对于 \(40\%\) 的数据，\(1 \le N \le 10^6\)。
对于 \(80\%\) 的数据，\(1 \le N \le 10^7\)。
对于 \(100\%\) 的数据，\(1 \le N \le 10^8\)。
对于 $ 10^8 $ 的数据 ，寻常的筛素数方法往往会TLE。
因此我们采用欧拉筛，来达到近似 O(n) 的时间复杂度
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e8 + 50;
int plist[N],cnt,n;
bool not_prime[N];
// plist[] 素数表 not_prime[] 标记表 true 为 合数 false 为素数
int main()
{
cin>>n;
for(int i=2;i<=n;i++)
{
if(not_prime[i] == false) plist[++cnt] = i;
for(int j = 1;j <= cnt;j++)
{
int x; x = i * plist[j];
if(x > n) break;// 超出 数据范围 直接停止循环
not_prime[x] = true; // 将 质数的倍数标记为 合数
if(i % plist[j] == 0) break; // i 只要找到一个素数因子 就可退出循环
}
}
cout<<cnt;
return 0;
}