Voici un algorithme simple pour générer tous les nombres premers,sans recours à la crible d'Ératosthène.Je l'ai écrit en Qbasic.
2-2^n mod n=0
le logiciel c'est Justbasic
rem Prim gen
for n= 1 to 1000
u=2-2^n mod n
if u mod n=0 then
print n
end if
next n
https://www.justbasic.com/download.html
Télécharger le logiciel free puis copier coller le paragraphe "rem Prim gen" .Il suffit de changer les valeurs 1000,10000,ETC... Pour obtenir la quantité recherchée.Tester et donner avis?
33 et 42 sont premiers ?
There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.
Bonjour.
Cette méthode est connue, mais échoue, par exemple avec 561=3*11*17 qui apparaît dans la liste. Voir nombre de Carmichael sur Wikipédia. elle est aussi très gourmande en place mémoire pour n grand.
Quant au programme, recalculer u modulo n alors que u est déjà modulo n est superfétatoire.
Cordialement.
33 42 explique ?
Pour ma part, ils ne sont pas sortis dans l'application de l'algorithme (j'ai repris quasiment le même avec Maple). 561, lui était présent.
les erreurs sont très minimes même si le 561 apparaît .Pour l'instant ils n'existe aucun algo au monde pour générer les premiers,hormis la crible d'Ératosthène.Je pense c'est le meilleur pour l'instant.Peut donner une explication sur la répatitions des premiers .Connu ou non connu .Si on a pas en main un algorithme ,en cherche un asturce.Il suffit de boucler un Test de primalitè tel AKS ou autre .Ici c est le bouclage du test AKS avec une simplfication .(x-1)^n-(x^n-1)=(x-1)^n-x^n+1=x-x^n.
GGO si vraiment vs comprener cela c'est vous êtes assez fort parceque c'est très difficiles .
si la somme des chiffres d'un nombre est égal a 6 ,le nombre est divisible par 3 .
3+3=6
4+2=6
33/3=11
42/3=14
ne sont pas premiers
la methode n'echoue pas il suffit de filtrer les nombres de carmichael tel 561.
voici une methode
Les nombres dont la somme de leurs chiffres 3 6 9 ,ils sont divisible par trois :
12=1+2=3
15 et 51
24 et 42
33
Pourquoi mélanger le test de divisibilité par 3, accessible a un écolier, à la question de la génération des nombres premiers. Avec les ordinateurs actuels, on a facilement la liste des premiers inférieurs à un milliard, et le temps le plus long est celui de l'affichage. Donc le choix de la méthode est vite fait. En fait, on ne s'intéresse plus qu'à des moyens de prouver la primalité de nombres de 100 à 200 chiffres assez rapidement pour les usages techniques (cryptographie, par exemple).
Il est facile de trouver des documents sur le sujet, y compris romancés, puis, si on veut vraiment faire œuvre utile (et pas refaire ce que des milliers de débutants ont fait), étudier sérieusement la théorie des nombres.
Cordialement.
Bonjour,
Vous devriez vous documenter un tant soit peu avant de sortir de telles affirmations...Envoyé par jean reaver
Je pense que l'on peut faire des mathématiques en amateur, ce que je fait depuis longtemps et rechercher des démonstrations déjà faites de nombreuses fois, cela me donne un certain plaisir dont je ne me lasse pas. Est-ce vraiment faire oeuvre utile ? J'avoue ne pas me poser la question, oeuvre aussi utile certainement que celui qui fait des mots croisés ou lit des roman policiers.
@jean reaver
on ne peut que vous féliciter de pratiquer à votre niveau, en amateur, des mathématiques et plus précisément de l'Arithmétique et, vous encourager dans cette voie. Cependant, il faut que vous compreniez que les mathématiques que vous pratiquez sont élémentaires (niveau Lycée), très loin des niveaux de recherche actuel. Ainsi, vous utilisez le Petit théorème de Fermat, connu depuis le 17e siècle, sur lequel des générations de mathématiciens ont certainement dit tout ce qu'il y avait à dire d'élémentaire à son sujet. De plus, vous utilisez la réciproque de ce théorème qui est fausse. Il serait bien, pour votre progression futur, de tenir compte des avis qui vous sont donnés et comme dit plus haut de vous documenter quelque peu sur les questions que vous cherchez. Que ceci ne vous empêche pas de continuer vos recherches, mais en gardant à l'esprit que d'autres les ont déjà résolu depuis longtemps.
En mathématiques, la recherche de formules exactes donnant tous les nombres premiers (ou même donnant uniquement certains des nombres premiers) s'est généralement avérée vaine, ce qui a amené à se contenter de formules approchées.
que dire alors de la formule de Minac?
https://forums.futura-sciences.com/s...-premiers.html
m@ch3
Never feed the troll after midnight!
@ eudea
Est ce que vous avez testé l'algo sur le logiciel que j'ai mis ?Puis de raconter des choses?le reciproque du petit theorème de fermat donnent tous les nombres premiers.Mais Ils sont associé avec les nombres de carmichael tel le 561,1 729 ...etc
Si 2^(n-1) mod n = 1 est vrai .Alors le reciproque c'est faux.Le reciproque est vrai si a-a^n mod n=0 remarque la différence ?! entre le 1 et 0.J'ai trvaillé sur pour qu'il soit vrai je suis arrivé à ces conclusions.
rem Prim gen
for n= 1 to 1000
u=2-2^n
if u mod n=0 then
print n
end if
next n
copie coller sur l'application
Pourquoi republier un algorithme qui ne marche pas ? Et ça t'a été expliqué.
Tu fais tout ce qu'il faut pour qu'on ne te prenne pas au sérieux, dommage !
la formule qui "simule" le crible d’Ératosthène
bonjour
Il existe une variante du test de Fermat, le test de Miller Rabin, beaucoup plus efficace.
On peut tester la primalité d'un nombre n simplement, rapidement, et de manière déterministe jusqu'à n=3317044064679887385961981 (voir la suite OEIS A014233)
Au delà, on peut garder un test déterministe, mais cela suppose d'admettre l'hypothèse du continu généralisée et le temps de test peut être prohibitif.
Sinon, on peut utiliser le test de manière probabiliste, tout en sachant calculer un majorant de la probabilité de se tromper
Dernière modification par jall2 ; 06/09/2018 à 10h38.
erreur, c'est pas l'hypothèse du continu, mais l'hypothèse de Riemann
des modèles comme ça, on en voit plein, mais une seule erreur suffit à "casser" l'algorithme de base.
bon courage ! d'autant que plein d'autres avant toi ont bossés la dessus ! ( peut être ignores tu leurs travaux ? )
Concernant l'algoritm de carmichael :
p=6*n+1
q=12*n+1
r=18*n+1
N=p*q*r
si p,q et r sont premiers
ex:1729
(6*1+1)(12*1+1)(18*1+1)
7*13*17
Est qu'l les donnent tous ou bien non ?
le petit théorème de fermat c'est : a^(n-1) mod n=1
a etant la base
n est le nombre que l'on doit tester
si n est premier c'est toujours =1,dans toutes les bases.
Si n est diffrent de 1 ,alors est premier.Mais Ils existes des nombres qui affichent
le même résultat,par conséquent égal à 1.Ce qu'on désigne par pseudo premiers.
J'apporte la correction :FERMAT ne précise pas ou se trouve la vérité.On se conte d'une
seule ,puis on dit que c'est faux !il faut passer par plusieurs bases .le test est détérmiste.
ex:la valeur de 23 est 1 dans toutes les bases,jusqu'a n-1.
Voci le test de 91 .sachant que c'est un nombre composé.
base a reste modulaire
1 1
2 64
3 1
4 1
5 64
6 64
7 77
8 64
9 1
10 1
11 64
12 1
13 78
14 14
15 64
16 1
17 1
18 64
19 64
20 64
21 77
22 1
23 1
24 64
25 1
26 78
27 1
28 77
29 1
30 1
31 64
32 64
33 64
34 64
35 14
36 1
37 64
38 1
39 78
40 1
41 64
42 14
43 1
44 64
45 64
46 64
47 64
48 1
49 14
50 64
51 1
52 78
53 1
54 64
55 1
56 14
57 64
58 64
59 64
60 64
61 1
62 1
63 77
64 1
65 78
66 1
67 64
68 1
69 1
70 77
71 64
72 64
73 64
74 1
75 1
76 64
77 14
78 78
79 1
80 64
81 1
82 1
83 64
84 77
85 64
86 64
87 1
88 1
89 64
90 1
Si (mod)n est >1 ,alors est composé(corrig).
A mon avis je pense qu'il y a une erreur d'incompréhension du théorème et
moi j'ai fait cela.Tant qu'on parle de pseudo premiers !!!!
Si o<a<(n-1) et pour tout a^(n-1) mod n =1,alors n est un nombre premier.
input "test ";n
for a=1 to (n-1)
u=a^(n-1) mod n
print a,u
next a
si chaque sortie égal à 1 : c'est premier .Tester de petit nombres.
Oui, "'il y a une erreur d'incompréhension du théorème"; de ta part.
Le théorème dit "si n est premier, ...". la réciproque est fausse.
Et pour des petits nombres, il y a des algorithmes tellement plus rapides ...
Avec a-a^(n-1)mod n=0 (n'est pas tout à fait le reciproque) .On générer tous les nombres premiers et les pseudo premiers.
1
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
341
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
561
563
569
571
577
587
593
599
601
607
613
617
619
631
641
643
645
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997
L'algo marche bien .L'erreur c'est les nombres carmichael dont le 561.
Cet erreur revient au fait Que pour savoir si est premier ou non ,on doit tester dans tout base (a) jusqu'a (n-1).Par conséquent ,on passe les pseudos .JE sais que le reciproque est faux.
a-a^(n-1)mod n=0 n'est pas le reciproque.
Si la reciproque est fausse cela revient dire qu'on ne peut pas générer des prmiers.Ici ce n'est pas le cas.
voir la liste que j'ai posté .
ben , pourquoi insister, la réciproque est bien fausse puisque tu cites toi même les nombres de Carmichel !
il n'a d'ailleurs pas démontré la réciproque, ce qui est bien normal.par ailleurs, Fermat l'a énoncé en 1640 ! ça fait un bail quand même.
Il y a eu bien plus productif sur les nb premiers depuis.
Sur 1000 nombres premiers ,en verifiant la liste :341;561;625 sont pseudo premiers.
