除了简单地实现具有时间复杂度O（N log log N）的Eratosthenes筛网之外，我还尝试实现具有时间复杂度O（N）的修改。尽管两者都能产生预期的结果，但是与下一个相比，较早的一个花费的时间要少得多，我无法弄清原因。我对此非常感谢。
实施1：
def build_sieve_eratosthenes(num):
## Creates sieve of size (num+1) to correct for 0-indexing.
primes_sieve = [1] * (num+1)
primes_sieve[0] = primes_sieve[1] = 0
for p in range(2, num):
if primes_sieve[p] == 1:
for mul in range(2*p, num+1, p):
primes_sieve[mul] = 0
return primes_sieve
实施2：
def build_sieve_eratosthenes_linear(num):
## Creates sieve of size (num+1) to correct for 0-indexing.
primes_sieve = [1] * (num+1)
primes_sieve[0] = primes_sieve[1] = 0
## Builds a list of size (num+1) recording the smallest prime factor of each number.
SPF = [1] * (num+1)
## Builds a list of all primes seen so far with pos indicator of position where to insert the next prime.
## Uses a large fixed memory allocation scheme to avoid the usage of append list operation.
primes = [0] * num
pos = 0
for p in range(2, num+1):
if primes_sieve[p] == 1:
primes[pos] = p
pos = pos + 1
## Smallest prime factor of a prime is a prime itself.
SPF[p] = p
for i in range(0, pos):
if p * primes[i] <= num and primes[i] <= SPF[p]:
primes_sieve[p*primes[i]] = 0
SPF[p * primes[i]] = primes[i]
else:
break
return primes_sieve
test_num = 2000000
测试方法
def find_sum_of_primes_upto_num_with_sieve(sieve, num):
primes_sieve = sieve(num)
primes_sum = 0
for n in range(len(primes_sieve)):
if primes_sieve[n] == 1:
primes_sum = primes_sum + n
return primes_sum
结果：
start2 = time.time()
sum_2 = find_sum_of_primes_upto_num_with_sieve(build_sieve_eratosthenes, test_num)
end2 = time.time()
print("Sum of primes obtained: ", sum_2)
print("Time taken by checking primality of each number is %f sec" % (end2 - start2))
获得的素数总和：142913828922检查每个数字的素性所花费的时间为0.647822秒]
start3 = time.time()
sum_3 = find_sum_of_primes_upto_num_with_sieve(build_sieve_eratosthenes_linear, test_num)
end3 = time.time()
print("Sum of primes obtained: ", sum_3)
print("Time taken by checking primality of each number is %f sec" % (end3 - start3))
获得的素数总和：142913828922检查每个数字的素性所花费的时间为1.561308秒
我在每个例程中放置了一个简单的迭代计数器，并从10 ^ 3到10 ^ 7运行10的幂
build_sieve_eratosthenes：
1000 has 1958 iterations in sieve
10000 has 23071 iterations in sieve
100000 has 256808 iterations in sieve
1000000 has 2775210 iterations in sieve
10000000 has 29465738 iterations in sieve
build_sieve_eratosthenes_linear：
1000 has 831 iterations in sieve_linear
10000 has 8770 iterations in sieve_linear
100000 has 90407 iterations in sieve_linear
1000000 has 921501 iterations in sieve_linear
10000000 has 9335420 iterations in sieve_linear
您的linear函数是非线性的：请注意，内部循环运行pos次...而pos是找到的质数的计数，它是非一个常数。
linear比“正常”函数增长得慢，并且总体上迭代次数少得多。但是，每次迭代的成本都较高，这就是为什么您看到“反转”时间的原因。在linear函数中，找到的每个数字和每个“除法”都更昂贵；增长放缓并没有赶上您的2 * 10 ^ 6的限制，而不是我的10 * 7的限制。如果可以的话，您可以推断出大约一天的时间，以便更好地了解适当的时间...但是，中心的“问题”是每个数字的处理速度较慢。
对于细节感兴趣，这是完整的输出：
1000 has 1958 iterations in sieve
Sum of primes obtained: 76127
Time taken by checking primality of each number is 0.000904 sec
10000 has 23071 iterations in sieve
Sum of primes obtained: 5736396
Time taken by checking primality of each number is 0.008270 sec
100000 has 256808 iterations in sieve
Sum of primes obtained: 454396537
Time taken by checking primality of each number is 0.067962 sec
1000000 has 2775210 iterations in sieve
Sum of primes obtained: 37550402023
Time taken by checking primality of each number is 0.428727 sec
10000000 has 29465738 iterations in sieve
Sum of primes obtained: 3203324994356
Time taken by checking primality of each number is 5.761439 sec
1000 has 831 iterations in sieve_linear
Sum of primes obtained: 76127
Time taken by checking primality of each number is 0.001069 sec
10000 has 8770 iterations in sieve_linear
Sum of primes obtained: 5736396
Time taken by checking primality of each number is 0.010398 sec
100000 has 90407 iterations in sieve_linear
Sum of primes obtained: 454396537
Time taken by checking primality of each number is 0.107276 sec
1000000 has 921501 iterations in sieve_linear
Sum of primes obtained: 37550402023
Time taken by checking primality of each number is 1.087080 sec
10000000 has 9335420 iterations in sieve_linear
Sum of primes obtained: 3203324994356
Time taken by checking primality of each number is 11.008726 sec