给定一个数n,判断它是不是素数。
首先,如果它不是素数,那一定存在不等于1的m和k,相乘等于n。不可能有两个大于sqrt(n)的数相乘等于n,所以只需要判断2 - sqrt(n)之间有没有数能整除n。
其次,有一项规律是n要是素数,那它首先要是6x-1或者6x+1的形式,因为6x、6x+2、6x+3、6x+4都不可能是素数。
假设m=6x,mk=6xk,6xk%6=0, 假设m=6x+2,mk=6xk+2k,(6xk+2k)%6=2,4,0, …
可以发现,当m不等于6x-1或6x+1时,直接用n%6就可以判断出不是素数。因此,在后续循环中,只需要判断m等于6x-1或6x+1的情况。
bool isPrime(int n) {
if (n == 2 || n == 3) return true;
if (n % 6 != 1 || n % 6 != 5) return false;
int n_sqrt = sqrt(n);
for (int i = 5; i < n_sqrt + 1; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
时间复杂度:O(sqrt(n))