A23752. 数字选取
填空题
困难
知识点
题目描述
数字选取
题目描述
给定正整数 ，现在有1,2,...,n共计n个整数。你需要从这n个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最大公因数为 1）。请你最大化所选取整数的数量。
例如，当n=9时，可以选择1,5,7,8,9共计5个整数。可以验证不存在数量更多的选取整数的方案。
输入格式
一行，一个正整数 n，表示给定的正整数。
输出格式
一行，一个正整数，表示所选取整数的最大数量。
样例
输入样例 1
6输出样例 1
4输入样例 2
9输入样例 2
5数据范围
对于 40% 的测试点，保证1≤n≤1000 。
对于所有测试点，保证1≤n≤105 。
参考答案
#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;
}
上一题
下一题