Jugement des nombres premiers par Python

J'ai essayé d'implémenter un jugement de nombres premiers 100 ou moins en utilisant python de 3 manières. Il montre également le temps nécessaire pour chacun.

① N'utilisez pas les fonctions intégrées autres que l'impression (hors temps)


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))

Résultat d'exécution

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

② Comment vérifier un par un

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))

Résultat d'exécution [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

③ Tamis Eratostenes

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))

Résultat d'exécution [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

En comparant le temps, ① et ② n'ont fondamentalement pas beaucoup changé. Cependant, la méthode (2) n'était pas stable car la vitesse était parfois proche de celle de (3). En comparaison, le résultat était que le programme (3) était le plus rapide de ceux-ci. C'est un algorithme appelé tamisage Eratostenes, mais c'est probablement parce qu'il était très efficace et que la quantité de calcul était faible (j'ai fait référence au wiki, donc je posterai un lien).

Même pour les programmes qui produisent les mêmes résultats, il est amusant d'essayer de les mettre en œuvre avec des idées différentes, alors j'aimerais continuer.

Wikipédia Eratostenes Sieve