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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
| """Calcule les nombres premiers
Usage:
======
6k1_nombres_premiers.py
- nb_de: entrée utilisateur premier nombre à chercher
- nb_jusque: entrée utilisateur dernier nombre à chercher
recherche des nombres premiers en utilisant différents filtres
"""
__authors__ = ("Christelle Triboulot")
__copyright__ = "Triboulot"
__date__ = "2023-07-02"
__version__= "1.0.4 version en évolution"
import time
import random
from typing import List
liste_nb_prem_fichier: List[int] = []
start_time = time.time()
def filtre_2_3_5_7(nb_de):
"""
filtre pour éliminer les multiples de 2, 3, 5, 7,
pour permettre d'utiliser les autres filtres sans résultats non voulu.
Pour le 5 et le sept, c'est juste une fantaisie de ma part.
Entre nb_de
Sortie : True False
"""
return (nb_de % 2 != 0 and nb_de % 3 != 0
and nb_de % 5 != 0 and nb_de % 7 != 0)
def filtre_6k1(nb_de):
"""
Teste si un nombre est de forme 6k+-1
où k est un entier naturel.
Paramètres
.........
nb : int - nombre à tester
retourne : bool - True si le nombre est de forme 6k+-1
False sinon.
"""
return (nb_de % 6 == 1 or nb_de % 6 == 5)
def filtre_fermat(nb_de):
"""
Test probabiliste basé sur le petit théorème de Fermat.
Paramètres
.........
nb : int - nombre à tester
retourne : bool - True si le nombre est probablement premier
False sinon.
"""
for x in range(3): #pour réduire le nombre de non-premier, répéter 3 fois
a = random.randint(2, nb_de-1)
if pow(a, nb_de-1, nb_de) != 1:
return False
return True
def filtre_erastosthenes(nb_de):
"""
divise avec tous les nombres pemiers pour voir se le nombre est premier.
Long, mais trouve tous les nombres premiers
Paramètres
.........
nb : int - nombre à tester
retourne : bool - True si le nombre est premier
False sinon.
"""
for i in liste_nb_prem_fichier:
if i > pow(nb_de, 1/2) + 1:
return True
elif nb_de % i == 0:
return False
elif i > pow(nb_de, 1/2):
return True
return True
dec = 0
decompte = 0
par_1000000=0
# Lire le fichier "nombres_prem.txt" et stocker les nombres premiers dans une liste
with open("nombres_prem.txt", "r") as f:
for line in f.readlines():
liste_nb_prem_fichier.append(int(line))
# Récupérer le dernier nombre premier trouvé
dernier_nb_prem = liste_nb_prem_fichier[-1]
# Ouvrir un fichier texte en mode append
with open("nombres_prem.txt", "a") as f:
nb_de = dernier_nb_prem + 1 # commencer à partir du dernier nombre premier trouvé + 1
print(nb_de-1)
nb_jusque = int(input(". Jusqu'à : "))
while nb_de <= nb_jusque:
#if par_1000000%1000000==0: #juste pour moi
# print(par_1000000)
if nb_de==2: # Juste pour mettre 2 dans liste_nb_prem_fichier... Vois si plus efficace
liste_nb_prem_fichier.append(2)
f.write(str(nb_de) + "\n")
print(nb_de)
if nb_de > 2: # passe par les différents filtres pour réduire avant le filtre d'Erastosthens... Voir si autres filtres
if ((nb_de in [2, 3, 5, 7]) or (filtre_6k1(nb_de)
and filtre_fermat(nb_de) and filtre_2_3_5_7(nb_de))):
dec += 1
if filtre_erastosthenes(nb_de):
liste_nb_prem_fichier.append(nb_de)
f.write(str(nb_de) + "\n")
print(nb_de)
decompte += 1
nb_de += 1
par_1000000+=1
f.close()
print("Il y a :",dec+1, "nombres premiers trouvés avant le dernier filtre")
print("Il y a :",decompte+1, "nombres premiers trouvés")
# Temps passé sur le programme
end_time = time.time()
elapsed_time = end_time - start_time
print("Le temps d'exécution du code est : {:.6f} secondes".format(elapsed_time)) |
Partager