欧拉筛和埃氏筛哪个是寻找质数最快的方法

学渣李某人

本文涉及基础知识不多, 主要是算法层面, 没有使用第三方库

欧拉筛和埃氏筛是两种不同的寻找质数的方法, 欧拉筛相对更难理解, 但, 欧拉筛真的是最快的质数寻找方式吗?

不是

埃氏筛代码如下:

def eratosthenes_sieve(n):
    primes = []
    flags = [True] * (n + 1)
    flags[0], flags[1] = False, False
    nums = range(n + 1)

    for i in range(2, int(n ** 0.5) + 1):
        if flags[i] == True:
            for j in range(2 * i, n + 1, i):
                flags[j] = False

    for i in range(n + 1):
        if flags[i]:
            primes += [nums[i]]
            
    return primes

欧拉筛代码如下 (原代码):

def euler_sieve(upper_bound):
    filter_ = [False for i in range(upper_bound + 1)]
    primeNumbers = []
    for num in range(2, upper_bound + 1):
        if not filter_[num]:
            primeNumbers.append(num)
            
        for prime in primeNumbers:
            if num * prime > upper_bound:
                break
            
            filter_[num * prime] = 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++, 数据量也不够, 如果有人运行得出不同结果, 欢迎发在下方
  

学渣李某人

沉的真快......
标题有那么吓人吗

fish_nian

不错

fish_nian

算法这种除非是系统的学习，一般人学习Python不会考虑这些的，虽然说计算时间会大于O^2，但是还行

学渣李某人

fish_nian 发表于 2021-7-10 16:04
算法这种除非是系统的学习，一般人学习Python不会考虑这些的，虽然说计算时间会大于O^2，但是还行

除了专门打OI类比赛的, 基本没人在意这个...

傻眼貓咪

我的代碼是採用試除法，小費馬定理和米勒-拉賓質數判定法寫的：

def isPrime(n, k = 5):
    from random import randint
    if n < 2: return False
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]:
        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)) # 極大數沒有問題