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

学渣李某人

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

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

不是

埃氏筛代码如下:

1. def eratosthenes_sieve(n):
   
2.     primes = []
   
3.     flags = [True] * (n + 1)
   
4.     flags[0], flags[1] = False, False
   
5.     nums = range(n + 1)
   
6. 
   
7.     for i in range(2, int(n ** 0.5) + 1):
   
8.         if flags[i] == True:
   
9.             for j in range(2 * i, n + 1, i):
   
10.                 flags[j] = False
    
11. 
    
12.     for i in range(n + 1):
    
13.         if flags[i]:
    
14.             primes += [nums[i]]
    
15.             
    
16.     return primes

复制代码

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

1. def euler_sieve(upper_bound):
   
2.     filter_ = [False for i in range(upper_bound + 1)]
   
3.     primeNumbers = []
   
4.     for num in range(2, upper_bound + 1):
   
5.         if not filter_[num]:
   
6.             primeNumbers.append(num)
   
7.             
   
8.         for prime in primeNumbers:
   
9.             if num * prime > upper_bound:
   
10.                 break
    
11.             
    
12.             filter_[num * prime] = True
    
13.             if num % prime == 0:
    
14.                 break
    
15.             
    
16.     return primeNumbers

复制代码

测量时间代码如下:

1. import time
   
2. 
   
3. num = 1000000
   
4. 
   
5. s1 = time.time()
   
6. euler = euler_sieve(num)
   
7. e1 = time.time()
   
8. delta1 = e1 - s1
   
9. 
   
10. s2 = time.time()
    
11. eratosthenes = eratosthenes_sieve(num)
    
12. e2 = time.time()
    
13. delta2 = e2 - s2
    
14. 
    
15. print(f'量级: {num}')
    
16. print(f'欧拉筛用时: {delta1}')
    
17. print(f'埃氏筛用时: {delta2}')
    
18. print(f'时间差: {delta1 - delta2}')
    
19. print(f'时间比: {delta1 / delta2}')

复制代码

输出如下:

• 电脑1(速度较快) + 百万量级
  
  1. 量级: 1000000
     
  2. 欧拉筛用时: 0.21872687339782715
     
  3. 埃氏筛用时: 0.09372806549072266
     
  4. 时间差: 0.12499880790710449   
     
  5. 时间比: 2.3336326451704807

  复制代码
  
  
• 电脑2(速度较慢) + 百万量级
  
  1. 量级: 1000000
     
  2. 欧拉筛用时: 0.635487586537008648
     
  3. 埃氏筛用时: 0.205665456564456546
     
  4. 时间差: 0.205665456564456546
     
  5. 时间比: 3.0899092008571882

  复制代码
  
  
• 电脑1 + 千万量级 (电脑2的千万量级没做)
  
  1. 量级: 10000000
     
  2. 欧拉筛用时: 2.2177467346191406
     
  3. 埃氏筛用时: 1.596726894378662
     
  4. 时间差: 0.6210198402404785   
     
  5. 时间比: 1.3889330369688158

  复制代码
  
  
• 电脑1 + 亿量级
  
  1. 量级: 100000000
     
  2. 欧拉筛用时: 22.43600082397461
     
  3. 埃氏筛用时: 17.96090292930603
     
  4. 时间差: 4.475097894668579   
     
  5. 时间比: 1.2491577351251508  

  复制代码
  
  
• 电脑2 + 亿量级
  
  1. 量级: 100000000
     
  2. 欧拉筛用时: 64.61267971992493
     
  3. 埃氏筛用时: 26.365909576416016
     
  4. 时间差: 38.24677014350891
     
  5. 时间比: 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类比赛的, 基本没人在意这个...

傻眼貓咪

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

1. def isPrime(n, k = 5):
   
2.     from random import randint
   
3.     if n < 2: return False
   
4.     for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]:
   
5.         if n % p == 0: return n == p
   
6.     s, d = 0, n-1
   
7.     while d % 2 == 0:
   
8.         s, d = s+1, d/2
   
9.     for i in range(k):
   
10.         x = pow(randint(2, n-1), d, n)
    
11.         if x == 1 or x == n-1: continue
    
12.         for r in range(1, s):
    
13.             x = (x * x) % n
    
14.             if x == 1: return False
    
15.             if x == n-1: break
    
16.         else: return False
    
17.     return True
    
18. 
    
19. print(isPrime(100524249167)) # 極大數沒有問題

复制代码