Discussion :

[Inzaguiz]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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.

[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

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

[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 ?

[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!

[Inzaguiz]

Bonjour,
J'ai quasiment finis 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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