Primzahlbeurteilung durch Python

Ich habe versucht, 100 oder weniger Primzahlen mit Python auf drei Arten zu implementieren. Es zeigt auch die jeweils benötigte Zeit.

① Verwenden Sie keine anderen integrierten Funktionen als Drucken (außer Zeit).


import time
n = 2

t1 = time.time()
while n <= 100:
    div = 0
    m = 1
    while m <= n:
        if n % m == 0:
            div += 1
        m += 1
    if div == 2:
        print(n)
    n += 1
time = time.time() - t1
print("time:{}".format(time))

Ausführungsergebnis

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 0.007971048355102539

② So überprüfen Sie nacheinander

import time

def ma(n):
    sosu_list = []
    t1 = time.time()
    for n in range(2,n + 1):
        div = 0
        for m in range(1,n + 1):
            if n % m == 0:
                div = div + 1
        if div == 2:
            sosu_list.append(n)
    print(sosu_list)
            
t1 = time.time()
ma(100)
time = time.time() - t1
print("time:{}".format(time))

Ausführungsergebnis [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] time:0.0027151107788085938

③ Eratostenes-Sieb

import time

def eratosu(n):
        sosu_list = []
        false = []
        for i in range(2,n+1):
            if i not in false:
                sosu_list.append(i)
                for j in range(i*i,n+1,i):
                    false.append(j)
        return sosu_list
    
t1 = time.time()
print(eratosu(100))
time = time.time() - t1
print("time:{}".format(time))

Ausführungsergebnis [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] time:0.0005650520324707031

Beim Vergleich der Zeit haben sich ① und ② im Grunde nicht viel geändert. Methode (2) war jedoch nicht stabil, da die Geschwindigkeit manchmal nahe an der von (3) lag. Im Vergleich dazu war das Programm (3) das schnellste davon. Es ist ein Algorithmus namens Eratostenes-Sieben, aber wahrscheinlich, weil er sehr effizient und der Rechenaufwand gering war (ich habe auf das Wiki verwiesen, also werde ich einen Link posten).

Selbst für Programme, die dieselben Ergebnisse liefern, macht es Spaß, sie mit unterschiedlichen Ideen umzusetzen, daher möchte ich fortfahren.

Eratostenes Sieve Wikipedia