判断一个数是质数的几种方法

质数也叫素数，是只能被1和它本身整除的正整数，最小的质数是2，目前发现的最大的质数是p=2^57885161-1【注1】。
判断一个数是质数的最简单的方法如下：

def isPrime1(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True

但是在上面的方法中有一些冗余的计算，所以做以下改进

def isPrime2(n):
	import math
	if n == 1:
		return False
	elif n < 4:
		return True
	else:
		r = int(math.floor(math.sqrt(n)))
		for i in range(2,r+1):
			if n % i == 0:
				return False
		return True

上面的方法对第一种方法做了一些改进，但是还可以再细分一些情况，如下：

def isPrime(n):
	import math
	if n == 1:
		return False
	elif n < 4:
		return True
	elif n & 1 == 0:
		return False
	elif n < 9:
		return True
	elif n %3 == 0:
		return False
	else:
		r = math.floor(math.sqrt(n))
		f = 5
		while f <= r:
			if n % f == 0:
				return False
			if n %(f+2) == 0:
				return False
			f += 6
		return True

判断15485863是否是素数时，三者的运行时间如下：

1.9960000515
0.0139999389648
0.0090000629425

4. 打表法：
可以事先列出M(M为正整数)下的素数表，判断一个数是否为素数时，可以直接在表中查找，这是最快的方法了，但是需要额外的存储空间，是一种用空间换取时间的方法。
下面是列出M以下的所有素数的一种方法。

def primeBelowM(m):
	num = [True for i in range(m)]
	for i in range(2,m):
		k = (m-1)/i
		for j in range(2,k+1):
			num[j*i] = False
	prime = []
	for i in range(2,m):
		if num[i]:
			prime.append(i)
	return prime

【注1】

引用

http://baike.baidu.cn/view/333373.htm