《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; }

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

相关推荐

多维聚合实战：超越GROUP BY的维度对齐与指标重权

PHP代码审计基础——超全局变量（三）

电容失效分析

更多资讯

电工证丢了异地好办电子证书怎么搞

220伏电工证怎么考？郑州报考避坑指南：实操考试心里没底怕挂科怎么办

湘乡哪里考电工证值不值得考？别交了冤枉钱

低学历也能报宿安特种作业操作证？含金量你得知道

宿安特种作业操作证2026河南最新政策下怎么快速拿证上岗

几年才能考高级电工证证丢了怎么补办

今日更新

西昌市电工作业查询怎么查？郑州报考避坑指南帮你少走弯路

西昌市电工作业查询通过率揭秘：怕考不过白交培训费？这几点要记牢

临夏电工证在哪里审官方报名入口怎么找

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？