欧拉筛和埃氏筛哪个是寻找质数最快的方法
本文涉及基础知识不多, 主要是算法层面, 没有使用第三方库欧拉筛和埃氏筛是两种不同的寻找质数的方法, 欧拉筛相对更难理解, 但, 欧拉筛真的是最快的质数寻找方式吗?
不是
埃氏筛代码如下:
def eratosthenes_sieve(n):
primes = []
flags = * (n + 1)
flags, flags = False, False
nums = range(n + 1)
for i in range(2, int(n ** 0.5) + 1):
if flags == True:
for j in range(2 * i, n + 1, i):
flags = False
for i in range(n + 1):
if flags:
primes += ]
return primes
欧拉筛代码如下 (原代码):
def euler_sieve(upper_bound):
filter_ =
primeNumbers = []
for num in range(2, upper_bound + 1):
if not filter_:
primeNumbers.append(num)
for prime in primeNumbers:
if num * prime > upper_bound:
break
filter_ = True
if num % prime == 0:
break
return primeNumbers
测量时间代码如下:
import time
num = 1000000
s1 = time.time()
euler = euler_sieve(num)
e1 = time.time()
delta1 = e1 - s1
s2 = time.time()
eratosthenes = eratosthenes_sieve(num)
e2 = time.time()
delta2 = e2 - s2
print(f'量级: {num}')
print(f'欧拉筛用时: {delta1}')
print(f'埃氏筛用时: {delta2}')
print(f'时间差: {delta1 - delta2}')
print(f'时间比: {delta1 / delta2}')
输出如下:
[*]电脑1(速度较快) + 百万量级
量级: 1000000
欧拉筛用时: 0.21872687339782715
埃氏筛用时: 0.09372806549072266
时间差: 0.12499880790710449
时间比: 2.3336326451704807
[*]电脑2(速度较慢) + 百万量级
量级: 1000000
欧拉筛用时: 0.635487586537008648
埃氏筛用时: 0.205665456564456546
时间差: 0.205665456564456546
时间比: 3.0899092008571882
[*]电脑1 + 千万量级 (电脑2的千万量级没做)
量级: 10000000
欧拉筛用时: 2.2177467346191406
埃氏筛用时: 1.596726894378662
时间差: 0.6210198402404785
时间比: 1.3889330369688158
[*]电脑1 + 亿量级
量级: 100000000
欧拉筛用时: 22.43600082397461
埃氏筛用时: 17.96090292930603
时间差: 4.475097894668579
时间比: 1.2491577351251508
[*]电脑2 + 亿量级
量级: 100000000
欧拉筛用时: 64.61267971992493
埃氏筛用时: 26.365909576416016
时间差: 38.24677014350891
时间比: 2.450614477481186
所以, 原因是什么?
我的推断:
1. 质数的分布: 质数的分布是非常不均匀的, 所以在数据量不足的情况下无法凸显出那个更快
2. 循环次数: 按照循环次数推断, 欧拉筛的时间复杂度是O(n^2), 埃氏筛是O(n^3/2)
仅代表个人观点, 没试过c++, 数据量也不够, 如果有人运行得出不同结果, 欢迎发在下方
沉的真快......
标题有那么吓人吗{:10_250:} {:10_275:}不错 算法这种除非是系统的学习，一般人学习Python不会考虑这些的，虽然说计算时间会大于O^2，但是还行 fish_nian 发表于 2021-7-10 16:04
算法这种除非是系统的学习，一般人学习Python不会考虑这些的，虽然说计算时间会大于O^2，但是还行
除了专门打OI类比赛的, 基本没人在意这个...{:10_262:} 本帖最后由 傻眼貓咪 于 2021-9-6 18:21 编辑
我的代碼是採用試除法，小費馬定理和米勒-拉賓質數判定法寫的：
def isPrime(n, k = 5):
from random import randint
if n < 2: return False
for p in :
if n % p == 0: return n == p
s, d = 0, n-1
while d % 2 == 0:
s, d = s+1, d/2
for i in range(k):
x = pow(randint(2, n-1), d, n)
if x == 1 or x == n-1: continue
for r in range(1, s):
x = (x * x) % n
if x == 1: return False
if x == n-1: break
else: return False
return True
print(isPrime(100524249167)) # 極大數沒有問題
页:
[1]