素数的定义素数是指一个大于 1 的自然数除了 1 和它自身外不能被其他自然数整除的数。函数整体逻辑该函数接收一个整数num作为参数通过一系列条件判断来确定这个数是否为素数。如果是素数则返回 1否则返回 0。int isprime(int num) { if (num 2) { return 0; } if (num 4) { return 1; } if (num % 2 0 || num % 3 0) return 0; int i 5; while (i * i num) { if (num % i 0 || num % (i 2) 0) { return 0; } i 6; } return 1; }基本原理大于 3 的素数都可以表示为6k ± 1的形式k为正整数。因为一个数可以表示为6k、6k 1、6k 2、6k 3、6k 4、6k 5这六种形式其中6k能被 2和3 整除6k 2能被 2 整除6k 3能被 3 整除6k 4能被 2 整除所以大于 3 的素数只能是6k 1或6k 5即6k - 1的形式。第一个大于3的素数是5此时k0但是1不是素数所以应该特判55之后的素数都是是以6k1的形式成对出现 。实际上对于k0时的这6个数不都大于3所以实际上是要单独判断k0的情况不能作为通式求解就好像数学是数列中a1是要特殊说明的。100 以内的素数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97 。形如6k ± 1的数当k为非负整数时在 100 以内的这些数有1,5, 7, 11, 13, 17, 19, 23,25, 29, 31,35, 37, 41, 43, 47,49, 53,55, 59, 61,65, 67, 71, 73,77, 79, 83,85, 89,91,95, 97不难发现排除掉k0和2的倍数、3的倍数 后100以内剩下的6k ± 1形的数中的非素数都是某个素数的倍数且是从5开始的所以只需要确保不是素数的倍数就可以了。因为素数是有无穷多个的也就有无穷多对所以为了代码简洁我们把单出来的5和下一对的7组成新的一对这样就不用单独再特判5了。代码各部分详细解释1. 处理小于 2 的数if (num 2) { return 0; }根据素数的定义素数是大于 1 的自然数所以小于 2 的数包括负数、0 和 1都不是素数直接返回 0。2. 处理 2 和 3if (num 4) { return 1; }因为小于 4 且大于等于 2 的数只有 2 和 3而 2 和 3 都是素数所以直接返回 1。3. 排除能被 2 或 3 整除的数if (num % 2 0 || num % 3 0) return 0;如果一个数能被 2 整除那么它是偶数除了 2 本身不是素数如果一个数能被 3 整除除了 3 本身也不是素数。所以当num能被 2 或 3 整除时直接返回 0。4. 检查大于 3 的可能因子int i 5; while (i * i num) { if (num % i 0 || num % (i 2) 0) { return 0; } i 6; }为什么每次增加 6大于 3 的素数都可以表示为6k ± 1的形式k为正整数。因为一个数可以表示为6k、6k 1、6k 2、6k 3、6k 4、6k 5这六种形式其中6k能被 6 整除6k 2能被 2 整除6k 3能被 3 整除6k 4能被 2 整除所以大于 3 的素数只能是6k 1或6k 5即6k - 1的形式。因此我们只需要检查6k ± 1形式的数是否能整除num即可。检查范围只需要检查到i * i num即可因为如果num有一个大于sqrt(num)的因子那么必然有一个小于sqrt(num)的因子与之对应。所以当i * i num时就不需要再继续检查了。5. 返回结果如果经过前面的所有检查都没有发现num的因子那么num是素数返回 1。总结该函数通过排除小于 2 的数、能被 2 或 3 整除的数然后只检查6k ± 1形式的数是否能整除num从而高效地判断一个数是否为素数。被《除数》整除《除数》能整除《被除数》应尽力减少重复代码所用时间用sqrtx来替代多次i * i 可以提高效率。bool isprime(int x) { if (x 2){return false;} if (x 4){return true;} if (x % 2 0 || x % 3 0){return false;} int x_ sqrt(x); for (int i 5;i x_;i 6) { if (x % i 0 || x % (i 2) 0){return false;} } return true; }