nombres premiers et apprendre à coder
Bonjour,
je suis en train d'apprendre Python, et j'ai créé un petit programme qui me permet de trouver les nombres premiers.
Je sais qu'il existe déjà une fonction math pour ça. Mais, je veux faire ça par moi-même pour apprendre et comprendre.
Je voulais savoir si il existe un moyen de remplacer ma liste "liste_nb_prem" par un fichier "fichier_nb_prem" qui ferait la même chose que la liste.
Est-ce que vous pourriez me mettre sur la piste.
Et que pensez-vous de mon programme/code.
merci de votre aide
Code:
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
| """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: 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:
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
nb_de = int(input("de : "))
nb_jusque = int(input(". Jusqu'à : "))
dec = 0
decompte = 0
par_1000000=0
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... Vois si plus efficace
liste_nb_prem.append(2)
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.append(nb_de)
print(nb_de)
decompte += 1
nb_de += 1
par_1000000+=1
print("Il y a :",dec+1, "nombres premiers trouvés avant le dernier filtre")
print("Il y a :",decompte+1, "nombres premiers trouvés")
print(liste_nb_prem)
# 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)) |
