你的分享就是我们的动力 ---﹥

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

时间:2013-05-20 13:42来源:www.chengxuyuans.com 点击:
质数也叫素数,是只能被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)/2
		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

转载注明地址:http://www.chengxuyuans.com/Python/61026.html

推荐文章