《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代码审计基础——超全局变量（三）

电容失效分析

更多资讯

PHP-Parser 在 enterNode 中替换节点为什么会无限递归？怎么避免

text-to-cad SRDF 技能深度解析：MoveIt2 机器人规划语义的编写、校验与烟雾测试

Multi-Agent架构改造实践：从传统Web到智能体驱动的前后端重塑

MCP Toolbox for Databases 中 bigtable-list-schemas 工具详解：一次获取 Bigtable 表、列族与 SQL 视图的完整 Schema

Google Developer Knowledge Skill：让 Agent 通过 MCP 与 REST API 检索官方 Google 开发者文档的实战指南

SSM+JSP母婴商城毕业设计：数据库脚本与部署全攻略

今日更新

51单片机开环控制磁阻传感器的硬件匹配与代码实现

AI Agent安全操作数据库：SQL注入防御与参数化查询实战

Android逆向实战：还原激励类App签到接口的签名算法

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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