《P14073 [GESP202509 五级] 数字选取》

题目背景对应的选择、判断题试题 - GESP 202509 C 五级 - 洛谷有题题目描述给定正整数 n现在有 1,2,…,n 共计 n 个整数。你需要从这 n 个整数中选取一些整数使得所选取的整数中任意两个不同的整数均互质也就是说这两个整数的最大公因数为 1。请你最大化所选取整数的数量。例如当 n9 时可以选择 1,5,7,8,9 共计 5 个整数。可以验证不存在数量更多的选取整数的方案。输入格式一行一个正整数 n表示给定的正整数。输出格式一行一个正整数表示所选取整数的最大数量。输入输出样例输入 #1复制6输出 #1复制4输入 #2复制9输出 #2复制5说明/提示对于 40% 的测试点保证 1≤n≤1000。对于所有测试点保证 1≤n≤105。代码实现#include iostream #include vector using namespace std; int main() { int n; cin n; if (n 1) { cout 1 endl; return 0; } vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; int cnt 0; for (int i 2; i n; i) { if (isPrime[i]) { cnt; if ((long long)i * i n) { for (int j i * i; j n; j i) { isPrime[j] false; } } } } cout cnt 1 endl; return 0; }