Python_算法实现_(8)埃拉托色尼筛选法-python黑洞网

本站消息

站长简介/公众号

出租广告位,需要合作请联系站长

dfh8374

1018

文章

825137

访问

+关注

分类

暂无分类

日期归档

2023-06(3)

Python_算法实现_(8)埃拉托色尼筛选法

发布于2019-08-20 11:00 阅读(1422) 评论(0) 点赞(21) 收藏(2)

1. 概念

埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。

在 i7 CPU（单线程）处理器下它可以在1s之内生成10^9以内的所有素数，因此，当这种筛选算法被应用的时候，它的速度是非常惊人的。

2. 步骤

先把1删除（现今数学界1既不是质数也不是合数）
读取队列中当前最小的数2，然后把2的倍数删去
读取队列中当前最小的数3，然后把3的倍数删去
读取队列中当前最小的数5，然后把5的倍数删去
读取队列中当前最小的数7，然后把7的倍数删去
如上所述直到需求的范围内所有的数均删除或读取

3. 实现代码

import numpy as np

def eratosthenes(n):
    p = np.arange(1,n+1,1)   # 生成1—n数组

    p[0] = 0    # 数字1不是质数单独处理
    i = 2       # i表示当前最小质数
    
    while i < n:   # i小于n时，i倍数的数字都不是质数，因此类推
        if p[i-1] != 0:
            j = i * 2
            while j < n+1:
                p[j-1] = 0
                j += i
        i += 1
        
    print(p)


eratosthenes(1000)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

输出结果为：

[  0   2   3   0   5   0   7   0   0   0  11   0  13   0   0   0  17   0
  19   0   0   0  23   0   0   0   0   0  29   0  31   0   0   0   0   0
  37   0   0   0  41   0  43   0   0   0  47   0   0   0   0   0  53   0
   0   0   0   0  59   0  61   0   0   0   0   0  67   0   0   0  71   0
  73   0   0   0   0   0  79   0   0   0  83   0   0   0   0   0  89   0
   0   0   0   0   0   0  97   0   0   0 101   0 103   0   0   0 107   0
 109   0   0   0 113   0   0   0   0   0   0   0   0   0   0   0   0   0
 127   0   0   0 131   0   0   0   0   0 137   0 139   0   0   0   0   0
   0   0   0   0 149   0 151   0   0   0   0   0 157   0   0   0   0   0
 163   0   0   0 167   0   0   0   0   0 173   0   0   0   0   0 179   0
 181   0   0   0   0   0   0   0   0   0 191   0 193   0   0   0 197   0
 199   0   0   0   0   0   0   0   0   0   0   0 211   0   0   0   0   0
   0   0   0   0   0   0 223   0   0   0 227   0 229   0   0   0 233   0
   0   0   0   0 239   0 241   0   0   0   0   0   0   0   0   0 251   0
   0   0   0   0 257   0   0   0   0   0 263   0   0   0   0   0 269   0
 271   0   0   0   0   0 277   0   0   0 281   0 283   0   0   0   0   0
   0   0   0   0 293   0   0   0   0   0   0   0   0   0   0   0   0   0
 307   0   0   0 311   0 313   0   0   0 317   0   0   0   0   0   0   0
   0   0   0   0   0   0 331   0   0   0   0   0 337   0   0   0   0   0
   0   0   0   0 347   0 349   0   0   0 353   0   0   0   0   0 359   0
   0   0   0   0   0   0 367   0   0   0   0   0 373   0   0   0   0   0
 379   0   0   0 383   0   0   0   0   0 389   0   0   0   0   0   0   0
 397   0   0   0 401   0   0   0   0   0   0   0 409   0   0   0   0   0
   0   0   0   0 419   0 421   0   0   0   0   0   0   0   0   0 431   0
 433   0   0   0   0   0 439   0   0   0 443   0   0   0   0   0 449   0
   0   0   0   0   0   0 457   0   0   0 461   0 463   0   0   0 467   0
   0   0   0   0   0   0   0   0   0   0 479   0   0   0   0   0   0   0
 487   0   0   0 491   0   0   0   0   0   0   0 499   0   0   0 503   0
   0   0   0   0 509   0   0   0   0   0   0   0   0   0   0   0 521   0
 523   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
 541   0   0   0   0   0 547   0   0   0   0   0   0   0   0   0 557   0
   0   0   0   0 563   0   0   0   0   0 569   0 571   0   0   0   0   0
 577   0   0   0   0   0   0   0   0   0 587   0   0   0   0   0 593   0
   0   0   0   0 599   0 601   0   0   0   0   0 607   0   0   0   0   0
 613   0   0   0 617   0 619   0   0   0   0   0   0   0   0   0   0   0
 631   0   0   0   0   0   0   0   0   0 641   0 643   0   0   0 647   0
   0   0   0   0 653   0   0   0   0   0 659   0 661   0   0   0   0   0
   0   0   0   0   0   0 673   0   0   0 677   0   0   0   0   0 683   0
   0   0   0   0   0   0 691   0   0   0   0   0   0   0   0   0 701   0
   0   0   0   0   0   0 709   0   0   0   0   0   0   0   0   0 719   0
   0   0   0   0   0   0 727   0   0   0   0   0 733   0   0   0   0   0
 739   0   0   0 743   0   0   0   0   0   0   0 751   0   0   0   0   0
 757   0   0   0 761   0   0   0   0   0   0   0 769   0   0   0 773   0
   0   0   0   0   0   0   0   0   0   0   0   0 787   0   0   0   0   0
   0   0   0   0 797   0   0   0   0   0   0   0   0   0   0   0 809   0
 811   0   0   0   0   0   0   0   0   0 821   0 823   0   0   0 827   0
 829   0   0   0   0   0   0   0   0   0 839   0   0   0   0   0   0   0
   0   0   0   0   0   0 853   0   0   0 857   0 859   0   0   0 863   0
   0   0   0   0   0   0   0   0   0   0   0   0 877   0   0   0 881   0
 883   0   0   0 887   0   0   0   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0 907   0   0   0 911   0   0   0   0   0   0   0
 919   0   0   0   0   0   0   0   0   0 929   0   0   0   0   0   0   0
 937   0   0   0 941   0   0   0   0   0 947   0   0   0   0   0 953   0
   0   0   0   0   0   0   0   0   0   0   0   0 967   0   0   0 971   0
   0   0   0   0 977   0   0   0   0   0 983   0   0   0   0   0   0   0
 991   0   0   0   0   0 997   0   0   0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56