本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P14073 [GESP202509 五级] 数字选取 - 洛谷【题目描述】给定正整数n nn现在有1 , 2 , … , n 1,2,…,n1,2,…,n共计n nn个整数。你需要从这n nn个整数中选取一些整数使得所选取的整数中任意两个不同的整数均互质也就是说这两个整数的最大公因数为1 11。请你最大化所选取整数的数量。例如当n 9 n9n9时可以选择1 , 5 , 7 , 8 , 9 1,5,7,8,91,5,7,8,9共计5 55个整数。可以验证不存在数量更多的选取整数的方案。【输入】一行一个正整数n nn表示给定的正整数。【输出】一行一个正整数表示所选取整数的最大数量。【输入样例】6【输出样例】4【算法标签】#普及- #质数【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 定义最大范围intn;// 输入的数字nintisprime[N];// 素数标记数组isprime[i]存储i的最小质因数mapint,intmp;// 用于记录已经统计过的质因数intmain(){// 输入数字ncinn;// 埃拉托斯特尼筛法预处理最小质因数for(inti2;iN;i){// 如果i是素数则标记其倍数if(isprime[i]0){for(intjii;jN;ji){// 如果j还没有被标记过则记录其最小质因数if(isprime[j]0){isprime[j]i;}}}}// 统计1到n范围内的素数个数intcnt0;for(inti1;in;i){if(isprime[i]0){cnt;}}// 统计1到n范围内合数的不同质因数个数for(inti1;in;i){// 如果是素数或者已经统计过该质因数则跳过if(isprime[i]0||mp[isprime[i]]1){continue;}// 标记该质因数已经统计过mp[isprime[i]]1;cnt;}// 输出结果素数个数 不同质因数个数coutcntendl;return0;}【运行结果】6 4