试除法素数判断

素数的定义

素数是指一个大于 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，此时k=0，但是1不是素数，所以应该特判5，5之后的素数都是是以6k+1的形式成对出现 。

实际上对于k=0时的这6个数不都大于3，所以实际上是要单独判断k=0的情况，不能作为通式求解，就好像数学是数列中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

不难发现，排除掉k=0和2的倍数、3的倍数 后，100以内剩下的6k ± 1形的数中的非素数都是某个素数的倍数（且是从5开始的），所以只需要确保不是素数的倍数就可以了。

因为素数是有无穷多个的，也就有无穷多对，所以为了代码简洁，我们把单出来的5和下一对的7组成新的一对，这样就不用单独再特判5了。

代码各部分详细解释

1. 处理小于 2 的数

if (num < 2) { return 0; }

根据素数的定义，素数是大于 1 的自然数，所以小于 2 的数（包括负数、0 和 1）都不是素数，直接返回 0。

2. 处理 2 和 3

if (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，从而高效地判断一个数是否为素数。（被《除数》整除，《除数》能整除《被除数》）

应尽力减少重复代码所用时间，用sqrt（x）来替代多次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; }