1. #基础写法,效率慢
import datetime
start = datetime.datetime.now()
prime_number = []
n = 100000
for i in range(2, n):
for j in range(2,i):
if i%j == 0:
break
else:
prime_number.append(i)
t_time = (datetime.datetime.now()-start).total_seconds()
print('用时:{}s,{}内的素数一共有{}个'.format(t_time, n, len(prime_number)))
print(prime_number)
用时:49.140267s,100000内的素数一共有9592个
改进1.
除了2 的偶数都不是素数 ,所以将2直接放在列表中,第7行改为for i in range(3,n,2),将步长设为2,跳过所有偶数;同时因为奇数不能被偶数整队,所以将第8行改成for j in range(3, i, 2)
import datetime
start = datetime.datetime.now()
prime_number = [2]
n = 100000
for i in range(3, n, 2):
for j in range(3, i, 2):
if i%j == 0:
break
else:
prime_number.append(i)
t_time = (datetime.datetime.now()-start).total_seconds(
|