上海计算机学会2026年5月月赛C++丙组T2 素数的判定

素数的判定题目描述给定一个不小于222的整数NNN请判断NNN是否为素数。如果是素数输出P表示 Prime Number否则输出C表示 Composite Number。素数也称之为质数是指除了111与它本身外没有其他因数的数。输入格式单个整数表示NNN。输出格式如果是素数输出P否则输出C。数据范围2≤N≤2,000,000,0002 \le N \le 2,000,000,0002≤N≤2,000,000,000样例输入 #117输出 #1P输入 #291输出 #2C题解第一人称我先来分析这道素数判定题目题目要求输入一个大于等于2的整数判断它是素数就输出P是合数就输出C。我的解题思路很直接根据素数定义一个数如果在2 ~ √n区间内存在能整除它的数那它一定是合数反之就是素数。因为如果n有大于其平方根的因数那必然会对应一个小于平方根的因数所以只需枚举到√n即可能大幅减少循环次数适配题目最大20亿的数据范围。下面是添加好注释的完整代码#includebits/stdc.husingnamespacestd;intmain(){// 定义变量n使用long long防止大数运算溢出longlongn;// 读取输入的整数ncinn;// 从2开始遍历只枚举到 i*i n等价于i√nfor(longlongi2;i*in;i){// 如果n能被i整除说明存在除1和自身外的因数是合数if(n%i0){// 输出合数标记CcoutC;// 直接结束程序无需继续判断return0;}}// 循环结束都没找到因数说明是素数输出PcoutP;return0;}代码思路详解头文件我使用了万能头bits/stdc.h可以包含所有常用库写代码更便捷。变量n选用long long类型因为题目数据最大到20亿避免int类型溢出问题。循环从i2开始终止条件设为i*i n这是素数判断的核心优化不用遍历到n本身。一旦发现n % i 0代表找到因数立刻输出C并退出程序。若整个循环执行完毕都没有找到因数证明该数是素数最后输出P。补充说明这份代码逻辑简洁能正常通过题目所有测试用例。对于偶数、大数素数、大数合数都可以正确判定循环最大执行次数仅约四万多次运行效率完全符合题目要求。