Détecteur de nombre premier

Version imprimable

Bonsoir à tous :p

Je suis en train de faire un testeur de nombre premier sur python. Des idées pour améliorer sa précision ou autres ?

Je peux expliquer mon code aussi ;)

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
Mode = input("Mode Manuel (M) / Mode Auto (A)")
if Mode == 'M' :
    Sujet = int(input("Nombre entier a tester :"))
elif Mode == 'A' :
    Sujet = 2**89 -1
else :
    print("Rien compris !")
 
 
print("Nous testons :", str(Sujet), "\n")
 
 
Test = 1
Diviseur = 0
Quotient = 0.0
Trop = 2
Progression = int((Test/Sujet)*100)
 
PasFinie = 0
 
while Test <= Sujet:
 
    while Diviseur < Trop :
 
        Quotient = Sujet/Test
 
        if Quotient > 1000000000000000 :
            Entier = int(Quotient) -1
 
        else :
            Entier = int(Quotient)
 
 
        if Quotient == Entier :
            Diviseur += 1
 
        Test += 1
 
        Place = int((Test/Sujet)*100)
 
        if Place != Progression :
            Progression = Place
            print(Progression, "%")
 
        Testeur = Test /1000000
 
        if Testeur == int(Testeur):
            print("Nous testons :", str(Sujet))
            print("On en est à :", Test)
            print(Place, "%", "\n")
 
    print("arret à :", Test)
 
    if Test != Sujet +1 :
        PasFinie = 1
        Test = Sujet + 1
 
    else :
        PasFinie = 0
 
if Diviseur == 2 and PasFinie == 0:
    print("OMG nombre Premier")
 
else :
    print("Arf")

12/02/2016, 18h06
tyrtamos

Bonjour,

Pour tester si un nombre est premier, la méthode par division est assez lente, mais on peut améliorer ton code.

Soit n le nombre dont on doit dire s'il est premier.

- si ce nombre est pair (n%2==0), il est premier si c'est 2, et non-premier sinon. Après ce test, on ne prendra que des diviseurs impairs à partir de 3 (3, 5, 7, ...)

- dans ces tests de division par nombre impair, il faut s'arrêter à la racine carrée de n: ce n'est pas la peine d'aller plus loin, car si on n'a pas trouvé de diviseur avant, on n'en trouvera pas après!

- une amélioration est de ne diviser que par des nombres premiers si on en a déjà une liste (2, 3, 5, 7, 11, 13, ...), au lieu de prendre tous les nombres impairs. On diminue ainsi le nombre de divisions.

Avec ça, on a déjà quelque chose qui marche pas mal. Disons qu'avec Python, on arrive à des temps acceptables jusqu'à environ 100 millions. Au delà, il faut passer à une méthode probabiliste comme celle de Miller-Rabin qui permet de tester des nombres de 600 chiffres en quelques secondes.
12/02/2016, 18h23
Inzaguiz

Merci beaucoup ! Je vais appliquer cela a mon code :) parce que le nombre que j'ai m'y en auto, bah j'y suis encore :lol:

Tu m'as donné une idée pour briser mon ennui ! je vais faire une sorte d'IA qui mémorise les nombres premiers qu'elle trouve puis elle cherche les autre avec les 3 méthodes la ^^ je sais pas si je vais m'ennuyer autant mais en tout cas ça à l'air marrant à faire :oops:
12/02/2016, 18h27
Inzaguiz

J'ai une autre question ! Si je divise par 2, 3, 7, 11 et 13, et que je n'ai pas d'entiers. alors j'attaque direct avec la divison par 15, 17 et les prochains impaires ? Je risque pas de rater un multiple ? :calim2:
12/02/2016, 18h52
tyrtamos

Si tu as une liste de nombres premiers obtenue par ailleurs, tu commences par l'utiliser (par exemple: [2,3,5,7,11,13]). Et si elle ne suffit pas, tu continues avec les nombres impairs suivants => 15, 17, 19, 21, etc... Tout ceci sans dépasser racine de n.

Au cas où il te manquerait le calcul de la racine entière de n, la meilleure méthode est celle de Héron d’Alexandrie: une méthode qui a 2000 ans!!! Elle est de plus facile à programmer.

Et oui, c'est très amusant! :D

Bonjour,
J'ai quasiment finis :D Juste 1 question (je pense que la réponse est oui... Juste pour être sûr ^^) : si on divise par des nombres premiers et qu'on s'arrête a la racine de n, est-ce que ça marche toujours ?

voila mon code :

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
def Test(Sujet) :
    B = open("Premier", "r")
    Liste = eval(B.readline().rstrip("\r\n"))
    B.close
 
    PremierOK = 0
    ImpaireOK = 0
 
    print("\nLe cas de :", Sujet,"\n")
 
    n = 0
    Test = Liste[n]
    Dernier = Liste[int(len(Liste)*0.60)]
    Diviseur = 0
 
    if Sujet % 2 == 0 :
        impaire = 0
 
    else :
        impaire = 1
 
    if impaire == 1 : 
 
        while Test <= Dernier :
 
            print("On test avec :", Test)
            Reste = Sujet % Test
 
            if Reste == 0 :
                Diviseur += 1
 
            n += 1
 
            if n != len(Liste) :
                Test = Liste[n]
 
            else :
                Test += 1
 
            if Diviseur == 1 :
                print(Sujet, "Exclu par la Liste\n")
                Test = Dernier + 1
 
        if Diviseur == 0 :
            print("La Liste Valide\n")
            PremierOK = 1
 
 
        Racine = Sujet**(1/2)
        Test = Dernier + 2
 
        while Test <= Racine and Diviseur == 0 :
 
            print("On test avec :", Test)
            Reste = Sujet % Test
 
            if Reste == 0 :
                Diviseur += 1
 
            Test += 2
 
            if Diviseur == 1 :
                print(Sujet, "Exclu par les Impaires")
                Test = Racine + 1
 
        if Diviseur == 0 :
            print("Les Impaires Valident\n")
            ImpaireOK = 1
 
    else :
        print("Il est paire lol x)")
 
    if ImpaireOK == 1 and PremierOK == 1 :
        print("Un nombre premier !\n")
 
        B = open("Premier", "r")
        Liste = eval(B.readline().rstrip("\r\n"))
        B.close
 
        Liste.append(Sujet)
 
        A = open("Premier", "w")
        A.write(repr(Liste)+"\r\n")
        A.close()
 
    else :
        print("Un nombre normal\n")
 
 
 
YOLO = input(str("Voulez-vous utilser la puissante IA traqueuse de Nombres Premier ? O/N\n"))
 
if YOLO == "O" :
    b = int(input("Combien de tour ? :D"))
    print("C'est parti !\n")
    YOLO = int(1)
 
else :
    print("Dommage")
 
if YOLO == 1 :
    A = open("Premier", "r")
    Liste = eval(A.readline().rstrip("\r\n"))
    A.close
 
    B = open("Sujet", "r")
    Sujet = eval(B.readline().rstrip("\r\n"))
    B.close
 
    a = 1
    while a <= b :
        B = open("Sujet", "r")
        Sujet = eval(B.readline().rstrip("\r\n"))
        B.close
 
        Test(Sujet)
        a += 1
 
        Sujet += 1
 
        A = open("Sujet", "w")
        A.write(repr(Sujet)+"\r\n")
        A.close()
 
        A = open("Premier", "r")
        Liste = eval(A.readline().rstrip("\r\n"))
        A.close

15/02/2016, 21h28
fifafou

Oui,cela marchera,mais quand tu peux,utilise des boucles for,qui sont beaucoup plus rapides.
16/02/2016, 10h56
Inzaguiz

Ok ! Mercii :D
Maintenant je vais faire un petit menu pour un programme multitâche autour des nombres premiers :3 Et oui u.u en vacances il faut bien s'occuper :lol:
16/02/2016, 11h21
fifafou

Ce que tu peut faire facilement,c'est un programme qui calcul les premier nombre premiers
16/02/2016, 12h04
Inzaguiz

Bah la mon ia elle compte jusqu'à l'infini et remplis sa liste. ce qui est plutôt pratique car cette banque de donnée je vais m'en servir pour ma 3e version.

-Je prévois de faire une extension qui permet de tester si le nombre est premier (un mashup du 1 et 2). Du coup si il est dans la liste bah il est premiers. Sinon je fais le test (version 2). Puis si par chance il est premier, il est ajouté à ma banque de donnée et je n'oublie pas de classer par ordre croissant ^^

Puis si je trouve autre chose, je ferai une version 4 :D