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)) |
nombres premiers et apprendre � coder
R�pondre avec citation
Envoy� par Natell
, voir le bouton pour clore la discussion.
Partager