判断素数

编程题

Posted by JAN on August 30, 2019

给定一个数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))