用Python计算一百万以内的质数

2009 11 30 07:40 PM 4390次查看

分类：Python 标签：Python

今天在JavaEye看到有人测试计算一百万以内的所有质数，于是我也写了个Python版的：
from time import clock

def calPrime(n):
	primes = []

	for i in xrange(3, n + 1, 2):
		max = int(i ** .5)
		for prime in primes:
			if prime > max:
				primes.append(i)
				break
			elif not i % prime:
				break
		else:
			primes.append(i)

	if n >= 2:
		primes.insert(0, 2)

	return primes

c = clock()
primes = calPrime(1000000)
print clock() - c
#print primes
print len(primes)
说实话这是我第一次发现for循环的else的作用，如果没有的话，我得加个变量来表示。
经测试，这个程序用了2.481秒，还算不错。

接着改写成Cython：
def calPrime(int n):
	cdef list primes = []
	cdef int max = 0

	for i in xrange(3, n + 1, 2):
		max = i ** .5
		for prime in primes:
			if prime > max:
				primes.append(i)
				break
			elif not i % prime:
				break
		else:
			primes.append(i)

	if n >= 2:
		primes.insert(0, 2)

	return primes
成绩提高到了1.046秒。

顺带一提，从多次测试结果来看，计算时间复杂度是大概是O(2.5log2N)。

本想测试下C的速度，发现代码实在太麻烦了，整整多了一倍，就懒得放出来了。

2条评论 你不来一发么↓ 顺序排列 倒序排列

    向下滚动可载入更多评论，或者点这里禁止自动加载。

    想说点什么呢？