|
|
发表于 5-3-2009 11:14 AM
|
显示全部楼层
抱歉，看來之前是我有所誤會
我重新看囘所有帖子發現樓主的O(n ^ 2)是指brute force method而言
至於樓主本身的方法則是O(n ^ 1.5)也正因此比brute force method快
sieve of eratosthenes的複雜度很難計算
wiki上的資料是O((n log n)(log log n))
以下是用python寫的不同方法：
import timeit
import math
def findPrimesV1(total):
primearr = []
for i in xrange(2, total):
prime = True
for j in xrange(2, i):
if i % j == 0:
prime = False
break
if prime:
primearr.append(i)
return sum(primearr)
def findPrimesV2(total):
primearr = []
for i in xrange(2, total):
prime = True
for j in xrange(2, int(math.sqrt(i)) + 1):
if i % j == 0:
prime = False
break
if prime:
primearr.append(i)
return sum(primearr)
def findPrimesV3(total):
primearr = range(0, total)
for i in xrange(2, total):
if primearr:
for k in xrange(2 * i, total, i):
primearr[k] = 0
return sum(primearr) - 1
print 'sum < 10000 primes using bruce force method : %.2f' % timeit.Timer('findPrimesV1(10000)', 'from __main__ import findPrimesV1').timeit(1)
print 'sum < 10000 primes using square root method : %.2f' % timeit.Timer('findPrimesV2(10000)', 'from __main__ import findPrimesV2').timeit(1)
print 'sum < 10000 primes using sieve of eratosthenes : %.2f' % timeit.Timer('findPrimesV3(10000)', 'from __main__ import findPrimesV3').timeit(1)
print
print 'sum < 20000 primes using bruce force method : %.2f' % timeit.Timer('findPrimesV1(20000)', 'from __main__ import findPrimesV1').timeit(1)
print 'sum < 20000 primes using square root method : %.2f' % timeit.Timer('findPrimesV2(20000)', 'from __main__ import findPrimesV2').timeit(1)
print 'sum < 20000 primes using sieve of eratosthenes : %.2f' % timeit.Timer('findPrimesV3(20000)', 'from __main__ import findPrimesV3').timeit(1)
print
print 'sum < 100000 primes using square root method : %.2f' % timeit.Timer('findPrimesV2(100000)', 'from __main__ import findPrimesV2').timeit(1)
print 'sum < 100000 primes using sieve of eratosthenes : %.2f' % timeit.Timer('findPrimesV3(100000)', 'from __main__ import findPrimesV3').timeit(1)
print
print 'sum < 200000 primes using square root method : %.2f' % timeit.Timer('findPrimesV2(200000)', 'from __main__ import findPrimesV2').timeit(1)
print 'sum < 200000 primes using sieve of eratosthenes : %.2f' % timeit.Timer('findPrimesV3(200000)', 'from __main__ import findPrimesV3').timeit(1)
print
print 'sum < 2000000 primes using sieve of eratosthenes : %.2f' % timeit.Timer('findPrimesV3(2000000)', 'from __main__ import findPrimesV3').timeit(1)
在我電腦上的計算結果如下：
sum < 10000 primes using bruce force method : 0.78
sum < 10000 primes using square root method : 0.03
sum < 10000 primes using sieve of eratosthenes : 0.00
sum < 20000 primes using bruce force method : 2.88
sum < 20000 primes using square root method : 0.07
sum < 20000 primes using sieve of eratosthenes : 0.01
sum < 100000 primes using square root method : 0.50
sum < 100000 primes using sieve of eratosthenes : 0.05
sum < 200000 primes using square root method : 1.21
sum < 200000 primes using sieve of eratosthenes : 0.10
sum < 2000000 primes using sieve of eratosthenes : 1.48
如果是用編譯語言會更快，除了bruce force method以外應該都會滿足1秒以内計算出的條件 |
|
本周最热论坛帖子
楼主
是好的C programmer
这间公司是做Telco service的。可以学很多Telco standard的东西。
1665 
32
