4724: 【GESP2509五级】数字选取
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
样例输入 复制
6样例输出 复制
4提示
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n, p[N], cnt;
bool np[N];
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
if (!np[i]) p[++cnt] = i;
for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
np[i * p[j]] = 1;
if (i % p[j] == 0) break;
}
}
printf("%d\n", 1 + cnt);
return 0;
}