题解：洛谷 P14073 [GESP202509 五级] 数字选取

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P14073 [GESP202509 五级] 数字选取 - 洛谷

【题目描述】

给定正整数n nn，现在有1 , 2 , … , n 1,2,…,n1,2,…,n共计n nn个整数。你需要从这n nn个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最大公因数为1 11）。请你最大化所选取整数的数量。

例如，当n = 9 n=9n=9时，可以选择1 , 5 , 7 , 8 , 9 1,5,7,8,91,5,7,8,9共计5 55个整数。可以验证不存在数量更多的选取整数的方案。

【输入】

一行，一个正整数n nn，表示给定的正整数。

【输出】

一行，一个正整数，表示所选取整数的最大数量。

【输入样例】

6

【输出样例】

4

【算法标签】

#普及- #质数

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;// 定义最大范围intn;// 输入的数字nintisprime[N];// 素数标记数组，isprime[i]存储i的最小质因数map<int,int>mp;// 用于记录已经统计过的质因数intmain(){// 输入数字ncin>>n;// 埃拉托斯特尼筛法预处理最小质因数for(inti=2;i<N;i++){// 如果i是素数，则标记其倍数if(isprime[i]==0){for(intj=i+i;j<N;j+=i){// 如果j还没有被标记过，则记录其最小质因数if(isprime[j]==0){isprime[j]=i;}}}}// 统计1到n范围内的素数个数intcnt=0;for(inti=1;i<=n;i++){if(isprime[i]==0){cnt++;}}// 统计1到n范围内合数的不同质因数个数for(inti=1;i<=n;i++){// 如果是素数或者已经统计过该质因数，则跳过if(isprime[i]==0||mp[isprime[i]]==1){continue;}// 标记该质因数已经统计过mp[isprime[i]]=1;cnt++;}// 输出结果：素数个数 + 不同质因数个数cout<<cnt<<endl;return0;}

【运行结果】

6 4