RECHERCHE DE NOMBRES PREMIERS
MadM@tt
Messages postés
2167
Date d'inscription
mardi 11 novembre 2003
Statut
Membre
Dernière intervention
16 juillet 2009
-
18 nov. 2004 à 18:14
MadM@tt Messages postés 2167 Date d'inscription mardi 11 novembre 2003 Statut Membre Dernière intervention 16 juillet 2009 - 23 juil. 2007 à 16:37
MadM@tt Messages postés 2167 Date d'inscription mardi 11 novembre 2003 Statut Membre Dernière intervention 16 juillet 2009 - 23 juil. 2007 à 16:37
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/27662-recherche-de-nombres-premiers
https://codes-sources.commentcamarche.net/source/27662-recherche-de-nombres-premiers
23 juil. 2007 à 16:37
Effectivement ! c'est vrai que ça doit accélerer le truc, enfin je n'ai plus utilisé ce programme depuis longtemps (notamment à cause de son inutilité ^^) donc je ne sais pas si ça me servira.
23 juil. 2007 à 11:28
Qui te parle de tester si le nombre est pair ?
Le 1er nombre premier est 2 ===>> tu l'inscris donc d'office.
Tu fais ensuite ta boucle d'ajout à partir de 3 et avec un step 2
Tu ne risques ainsi pas de balayer les pairs, non ?
19 juil. 2007 à 21:45
Pour VB gratuit, si on veux faire ça légalement c'est impossible :D
Pour Sunduram, pourquoi ne pas essayer ? mais je pense que doit y'avoir des articles sur internet qui doivent présenter les meilleurs algo pour ce genre de recherches (et voir les commentaires de cette source aussi !)
19 juil. 2007 à 20:30
Est ce que je peux faire tourner ce code sous Excel(vba)(Office2003).
Sinon Y aurit il un moyen d'avoir VB gratuitement.
Je crois aussi que l'idée de faire Sunduram ne doit pas être rapide sinon l'un d'entre vous l'aurait utilisée. donc j'abandonne ça.
Je ne vous dirais jamais assez combien je suis attaché à ce sujet.
Merci de votre compréhension et de vos réponses.
18 juil. 2007 à 20:38
Alors pour maestro1303 > euh j'en sais rien lol. L'idée parait bonne, après est-ce que ça serait plus rapide... Ben franchement j'en ai aucune idée.
jmfmarques > pour les nombres pairs ben tu veux tester comment qu'il est pair ? En le divisant par 2, donc ça revient (à peu près) au meme qu'avec une boucle for qui cherche à le diviser de 2 à n parce que il va tester en premier avec 2 et ça va pas passer.
A moins que t'ai une autre idée... ?
17 juil. 2007 à 20:19
Est ce que quelqu'un peut répondre à mon message précédent?
Merci infiniment!
15 juil. 2007 à 08:33
1) je mets la note de 10. Comment faire autrement (je fais la même chose que toi pour terouver des nombres premiers. j'entends pas là : même mécanisme, à 2 "poils" près).
2) tu peux diviser par 2 te temps de traitement, si tu veux ... car (mis à part le 1er nombre premier (2), tous les autres sont impairs et il est donc inutile de "balayer" les pairs).
Amitiés.
2 juin 2007 à 22:41
Au risque de dire une bêtise je me permets de vous demander ceci:
Il y a un algo (très facile à mettre en place) du à sudaram(crible de Sundaram) qui donne tous les nombres impairs... non premiers! Ne serait il pas plus facile de stocker ces nombres dans une table ou dans un fichier et trouver alors les nombres impairs ne figurant pas dans cette liste qui sont alors -à coup sûr - tous premiers!
16 janv. 2006 à 17:39
Le fichier tu le met bien ou tu veut, mais c'est plus simple de le mettre a la racine..
J'ai surtout poster pour montrer la différence de vitesse entre Vb et C, ca a rien a voir !
15 janv. 2006 à 21:15
(Je deviens parano depuis que je suis sous linux :-( ... Mais ça se comprend ^^)
15 janv. 2006 à 21:07
"et pour les linuxiens (ou mm les autres) la source ici :
(...)
Extractez (ou compilez) le .exe a la racine du disque (C:\), ensuite lancez l'invite de commande par demarrer - executer - cmd
puis faites des cd.. jusqu'a revenir a la racine (C:\) ensuite tapez votre commande sous cette syntaxe :"
Si on le met pas a la racine ça marche pas ? :D et puis comment on fait pour aller dans C:\ sur linux ? :D
Et executer cmd C:\ c'est pas plus simple que cmd -> cd.. -> cd.. -> ..... On peux faire cd \ aussi :D
Bon j'arrete mes conneries j'essaierais ça demain si j'arrive pas a requisitionner ma copine entre 2 examens :D
Sinon il y en a deja des tonnes d'eratostene je suis deja tomber sur un qui était particulierement bien fait au niveau de la gestion de la memoire etc...(ct sur cppfrance je pense) jte dirais ce que j'en pense
15 janv. 2006 à 20:30
VEUILLEZ COMPLETEMENT IGNOREZ MON PRECEDENT CODE, JAI FAIT UNE FAUTE DANS LE CODE SOURCE.. BREF OUBLIEZ !
Par contre j'ai trouvé sur le net, un programme pour chercher les nombres entiers se basant sur le crible d'Ératostène (je sais aps si on dit comme ça) et accrochez vous bien...
Le programme me trouve 100 000 000 Millions de nombres 1ers en 15 sec, 10 Millions en 1 sec, 1 Milliards en 10 min..
J'ai refait les tests chez un pote avec un pc nettement plus performant (Amd athlon 3200 +, 1 Go de ram) et il trouve 2 Milliards de nombres premiers en 5 min...
Seuleument 3 pb :
-Il enregistre dans un txt, ce qui génère des txt de 2.10 Go (si si !)
- Les variables sont déclarés en unsigned long int cce qui fait des valeurs max de 4 295 000 000 (je sais plus exactement), et donc pas plus haut, il faudrait pouvoir les déclarer en long double, ce qui serait nettement mieux..
- Il faut lancer le log par l'invite de commande, mais ca je vous l'explique après !
tout d'abord telecharger le ici :
http://bork0.free.fr/logs/premiers.rar
et pour les linuxiens (ou mm les autres) la source ici :
http://bork0.free.fr/logs/premiers-sources.rar
Extractez (ou compilez) le .exe a la racine du disque (C:\), ensuite lancez l'invite de commande par demarrer - executer - cmd
puis faites des cd.. jusqu'a revenir a la racine (C:\) ensuite tapez votre commande sous cette syntaxe :
start Chercheprime.exe nombre_max (ou Chercheprime correspond au nom de l'exe)
Si vous voulez cherchez 1 000 000 000 de nombres, tapez :
start Chercheprime.exe 1000000000
Ensuite, une fenetre s'ouvre, bon et la... le log vous avertit quand c'est fini paar une méchante erreur !!
regardez dan sle répertoire oue s le log, vous devriez avoir primetab.txt, ouvrez le et tadam !
(si vous faites des recherches de 3 Milliards de nombres, n'essayez meme pas d'ouvrir le txt, il fera 3 Go :S )
Vous pouvez faire des test et comparez :
mon pc : Amd atlhlon 2000+ (fréquence a 1666 Mhz) - 256 Mo de ram me trouve 100 000 000 en 17 sec.. et 1 Milliards en 10-15 min
Pc d'un pote (3200 +, 1 Go de ram) : 2 Milliards de nombres en 5 min..
Voila, enjoy !
15 janv. 2006 à 14:23
Je lui fait afficher le tout dans le console et voila ce que j'ai :
Veuillez entrer la limite de verification :
10
2
3
4
6
8
9
La verification est terminee :).
Je ne pense pas que ça ait un rapport mais je l'ai compiler avec mingw sous linux.
Sinon un conseil. Au niveau des performance ce sera encore mieux si tu utilise des entiers et des modulo au lieu d'une division sur des nombres a virgule flottante. Même si les nombre a virgule flottante te permette de verifier de plus grand nombre apres un moment les calculs seront incoherent du au fait que l'exposant sera trop grand. Le mieux serait d'utiliser une librairie pour gerer les grands entier. il y en a pas mal sur le net.
15 janv. 2006 à 10:53
J'ai refait le programme en C (c'est pas tout a fait le meme algo mais ca y ressemble) et les résultats sont vraiment flagrent !
Le programme me trouve 35 000 000 de nombres premiers en 10 sec...
Je vous poste le lien vers le progz ainsi que la source (je mt le tout dans un rar)..
Il existe des algo encore bien plus rapide, mais bien plus difficile a mettre en place, donc j'essaye pas trop :P
Au début le fichier enregistrait dans un fichier txt, mais d'une ca ralentissait, de 2 quand on arrive avec un fichier txt de 30 Mo en 3 sec, ca calme un peu..
Donc le programme vous dit juste le dernier nombre trouvé, si vous voulez quand meme que le log enregistre, dites le moi !
Ce n'est aps le meme genre de programme que celui ci, puisqu'on definit le nombre jusqu'ou il va chercher !
Assez blablaté, voici le lien :
http://bork0.free.fr/logs/premiers.rar
A+
4 nov. 2005 à 19:47
Chacun peut remanier la source comme il veut, j'avais aussi penser, pour afficher le résultat tout en gagnant le temps comme si je l'affichai pas : on gèle le rafraichissement de la textbox avec les api, on calcule et on ajoute normalement dans la textbox, mais ça prendra très peu de temps car la textbox n'est pas rafraichie, et par exemple on rafraichit la textbox toutes les 10 secondes....
Enfin y'a plein de techniques
Mais le manifest je savais pas que ça ralentissait le prog, et la sauvegarde, c'est comme la textbox, y'a vraiment moyen de l'améliorer quoi...
Enfin merci pour ton commentaire ;)
2 nov. 2005 à 14:46
Debut:
Number = NombreEnCours
' cherche
Liste.Visible = False
Do
If StopSearch = True Then GoTo Fin
' Afin de ne pas stocker trop de nombres dans la listbox on quitte et on revient
If Number - NombreEnCours > 99999 Then
NombreEnCours = Number
Liste.Clear
GoTo Debut
End If
If Premier(Number) Then Liste.AddItem Str(Number)
Number = Number + 1#
DoEvents
Loop
Fin:
Liste.Visible = True
btnStop.Enabled = False
Start.Enabled = True
NombreEnCours = Number
Save
NumberStart.Text = Trim(Str(NombreEnCours))
Me.Caption = "Fini !"
End Function
Voila je te donne mes résultats sur 20 seconde en partant de 1...
Original = 421010
Opti moyenne (sans thèmexp + liste invisible) = 1809972
Opti maximum = 2129262
Bon je sais que tu voulais pas enlever la fonction pour sauvegarder car si l'ordi plante.. m'enfin il va pas planter toutes les minutes quand meme !!!
A +
26 août 2005 à 14:15
autant pour moi
26 août 2005 à 10:27
Ta source nous a tous intéressé puisque je participais depuis longtemps à la discussion ;)
25 août 2005 à 23:12
25 août 2005 à 21:53
Pour la classe... aucune idée j'ai jamais utilisé de classe je n'ai pas commencé avec cette source, donc je ne sais pas du tout quoi de répondre désolé, essaye de recopier le code en copier collé sinon
A noter que j'ai fait ça sous VB5 c'est peut etre la le problème ??
Mindiell > lit la présentation de la source
Petit résumé : j'en avais envie, je m'ennuyai, ça me tentait etc etc etc... J'ai fait ça pour le plaisir et pour m'entrainer aussi, après bien sur tu peux me reprocher de l'avoir poster alors qu'il existe mieux et que je ré-ré-réinvente la roue ;) mais vu le nombre de commentaires, je pense que cette source a été interessante et le sera pour ceux qui cherchent des infos en venant ici
Voilà ;) bonne journée
25 août 2005 à 17:15
25 août 2005 à 17:11
C'est une source que je recherchait merci
mais j'ai un problème quand je clique sur ton exe, il y a message d'erreur qui dit:
"Erreur système &h80070583(-2147023485). La classe n'existe pas"
merci de m'aider
Bonne prog a tous.
26 avril 2005 à 14:08
26 avril 2005 à 14:01
26 avril 2005 à 13:53
26 avril 2005 à 12:49
enfin disons qu'on a tous des changements de projet des fois ;) mais si quelqu'un est motivé pour le faire je l'encourage !
26 avril 2005 à 11:28
26 avril 2005 à 11:23
bonne prog'
20 févr. 2005 à 12:56
20 févr. 2005 à 01:06
have fun pour la suite
7 févr. 2005 à 20:02
Sinon, faut avouer que c'est bien pensé. Moi aussi, j'avais fait un prog sur les nombres premiers, en Javascript, je crois, mais chais pas où je l'ai foutu !
Voili, voila un petit 10/10.
@++
9 janv. 2005 à 23:30
9 janv. 2005 à 18:19
si tu as :
a=b [p]
ca veut dire : il existe k un entier tel que :
a=k*p + b
bon, si je prend a=15 et p=2 alors, on pense tout de suite à :
15=7*2 +1
donc :
15=1 [2]
mais 15=6*2 + 3 c'est vrai aussi et donc on peut écrire :
15 = 3 [2]
ou même
15= -1 [2]
la pratique dit de prendre le plus petit entier en valeurs absolue de même signe que celui qui est devant le signe de congruence, mais ya des foi ou on fait autre chose.
9 janv. 2005 à 18:11
dnob700 >>
"(attention, ce n'est pas forcement le plus petit reste)."
c'est à dire?
scelw >>
ok..je verrai ca apres les examens. ^^
9 janv. 2005 à 18:07
si tu veux plus de précisions mail-moi (je passe rarement sur cppfrance)! :)
9 janv. 2005 à 17:56
si en vb tu écrit :
x=a mod b
(en c tu mettrai x=a%b; )
en math tu l'écrit :
a=x modulo b (avec le signe égale à trois branche)
ou en abrégé :
a=x [b] (avec le signe égale à trois branche)
c'est a dire que x est le reste de la division entière de a par b (attention, ce n'est pas forcement le plus petit reste).
il faut ausse remarquer que l'opération ne s'écrit pas dans le même ordre en math et en VB et que le signe égale spécial n'est pas obligatoire, on peut aussi bien écrire le signe normale.
9 janv. 2005 à 17:31
9 janv. 2005 à 17:21
9 janv. 2005 à 16:18
En fait ce qui pose problème c'est le symbole égale avec 3 barre au lieu de 2. En analyse ca donne l'equation d'une courbe mais là... j'ai vu ce symbole dans le 2eme tome de mon cours d'algebre qui traite des entier donc j'imagine que j'aurai plus d'info la dessus après les examens...
Je sais pas si tu as deja vu l'algo. faudrai que je retrouve l'adresse ou je l'ai trouver. je l'ai imprimer je devrai pouvoir retrouver ca
9 janv. 2005 à 16:10
amicalement
scelw
9 janv. 2005 à 15:44
9 janv. 2005 à 14:53
Deuxio, qui connait une bonne implémentation de l'algo des 3 indiens en VB ou C/C++ ?
12 déc. 2004 à 11:50
Donc, avis à tous les passionés, passez au C/C++ ! ça vaut vraiment le coup (je parle en connaissance de cause puisque j'ai commencé avec le VB avant de me convertir au C). et puis l'aide de NTL est en français et l'installation facile... n'hésitez pas !
2 déc. 2004 à 18:27
Si tu arrive à multiplier, moyennant quelque manipulation algebrique, au depart de l'algo la ça ira
2 déc. 2004 à 18:22
il faut évidemment un algorithme pour à chaque fois aller chercher une nouvelle décimale... Pensez vous qu'il est possible d'utiliser cette méhode :
je calcule Pi (avec un calcul précis) et je le multiplie en meme temps par 10
je prend la dernière décimale
je recalcule et remultiplie par 100
je prend la dernière décimale
etc avec à chaque fois 10 de plus, comme ça a chaque fois j'ai une décimale en plus
Pour calculer, j'ai des fonctions pour les grands nombres, mais je voulais savoir si cette methode est bonne, parce que j'avais déjà essayé de l'utiliser mais hélas sans succès (cétait il y a longtemps aussi).
Merci tous
1 déc. 2004 à 20:22
30 nov. 2004 à 21:05
30 nov. 2004 à 18:12
1. racine de deux ne se répète pas, et pourtant il est bien irrationnel mais pas transcendant, or pi est irrationnel (d'après Ramanujan ca a été établi) donc il ne se répète jamais et la preuve expérimentale de son irrationnalité ne fait aucun doute - et transcendant .
Le seul doute est celui de sa transcendance, que l'on n'a jamais démontrée, mais qui semble se vérifier d'elle meme alors que l'on trouve de plus en plus de décimales.
Pour la question plus haut, il y a un algorithme qui permet de calculer une nième décimale binaire et qui a été utilisée pour calculer la 10^100 ème décimale binaire de pi (qui est un 1) mais est bcp plus lente pour calculer une décimale binaire et absolument innéficace pour calculer la série...
En ce qui concerne les nb premiers, il y a une probabilité d'apparence donnée (avec ln je crois) qui constitue la fonction zeta. En ce qui concerne pi, aucune probabilité possible (du fait de sa transcendance) et notemment a cause du 0 qui est plutot rare (surtt dans les 1000 premieres...)
Enfin bcp de problèmes quoi :)
Vlad
30 nov. 2004 à 16:21
29 nov. 2004 à 23:56
Et dnob700, si PI ne se répète jamais, ca veut rien dire pour sa normalite. 0,01234657890123456789... est normal, mais pas irrationnel, non ?
29 nov. 2004 à 22:40
tout a la fin...
29 nov. 2004 à 22:11
un nombre normal est un irationnel pour qui chaque chiffre à la même fréquence d'apparition (donc 1/10ème dans son dévelloppement décimal (la suite des ses chiffres)).
Un nmbre parfaitement normal, est un nombre normal dans toute les bases.
Et dire que Pi ne se répète jamais c'est dire qu'il est normal, ce qui n'est pas prouvé. C'est a dire que l'on sait qu'il n'est pas périodique (sinon il serait rationel) mais rien ne prouve que toute les suite de chiffre finissent par apparaitre à un moment ou un autre.
29 nov. 2004 à 22:05
je sais plus ou j'ai vu ca je vais faire quelque recherche
29 nov. 2004 à 21:49
29 nov. 2004 à 19:20
Pour l'instant, et jusqu'à preuve du contraire, Pi est réel, irrationnel, transcendant (tout comme e)
Et jusqu'à preuve du contraire, on en est a plusieurs millions de milliards de décimales (binaires) et aucune répetition a l'horizon...
Vlad
29 nov. 2004 à 19:16
Ca voudrait dire que Pi est un nombre normal, et même si pour l'instant on a vraiment l'impression que c'est un nombre normal, ça n'a jamais pu être prouvé jusqu'à aujourd'hui.
29 nov. 2004 à 19:11
D'ailleurs, si on n'a jamais montré que ce nombre existait, on n'a pas non plus démontré qu'il n'existait pas - et Gauss, Cauchy et autres Fubini ont essayé de le trouver. Pourquoi pas nous :p ?
Quant à pi... on en a des expressions qu'il suffit de poursuivre un certain temps pour avoir la précision voulue... mais ca ne lui donne pas pour autant une logique ni une rationalité...
Vlad
29 nov. 2004 à 19:05
29 nov. 2004 à 18:52
Et puis bon, c'est comme tout le reste, moi ca me fait rever. Imagine que pi n'étant jamais répété, toutes les séquences de chiffre existe dedans à priori. Ainsi donc on devrait pouvoir y trouver la 9eme symphonie de Beethoven, ton prénom, le dernier bouquin en vogue, etc... :o)
29 nov. 2004 à 18:45
Vlad
29 nov. 2004 à 18:42
29 nov. 2004 à 18:41
29 nov. 2004 à 18:39
Je vais tacher de retrouver l'info, merci...
Ok, donc le Mp = 2^p -1, avec 2^p nombre pair possédant 70 facteurs premiers dont l'un d'eux serait supérieur à 10^300, là ca semble plus complexe déjà :o)
Je vais regarder ca...
29 nov. 2004 à 18:35
29 nov. 2004 à 18:33
les facteurs... alors ce nombre ne serait pas premier ... soit... donc hors-sujet... tu aurais pu avoir l'amabilité de me montrer cette erreur du doigt un peu avant ... faut dire que les torpilles aident pas a se souvenir... mille excuses ... recorrection : un nombre de mesrenne, impair et parfait dont le x de 2^x posséde 70 facteurs premiers au moins dont un supérieur à 10^300...
Vlad
29 nov. 2004 à 18:27
Ca te gene pas cette affirmation quand meme ? Un premier qui est parfait ?????
29 nov. 2004 à 18:22
J'ai éssayé de les rentrer dans le lecteur de disquette et mon ordinateur emet depuis un son de torpille...
Mais ca doit bien se trouver ailleurs je n'en doute pas
Vlad
29 nov. 2004 à 18:13
29 nov. 2004 à 17:55
il serait premier, impair, parfait supérieur à 10^300 et étant un nombre de mesrenne, soit le nombre 2^x-1, alors 2^x est un produit de 70 facteurs
Maitenant, je ne vois pas poi tu soutient que l'on l'aurait déjà trouvé ... le nombre en question peut etre supérieur à 100^10000000 je ne sais pas ...
Vlad (source: MIT, boston)
29 nov. 2004 à 17:51
Si ce n'est pas un Mersenne, on l'a peut-être déjà dépassé.
D'ailleurs, en y réfléchissant, un nombre parfait ne peut pas être premier puisqu'il vaut la somme de ses facteurs !!! :o)
Je reprends donc ton affirmation : "Un nombre impair et parfait existe peut-être..." :o)
D'ailleurs, s'il en existe au moins un, je doute qu'il n'en existe pas plusieurs....
29 nov. 2004 à 17:45
D'abord :
- tu parles d'un nombre premier, qui contiendrait des facteurs premiers... Tu m'expliques ? :o)
Ensuite, si c'est un nombre de Mersenne :
10^300 < 2^1500-1
Hors, on a trouvé le 31ème nombre de Mersenne premier : 2^1 398 269 -1 => 10^420 921
Donc on l'aurait déjà trouvé !
Donc ton affirmation est fausse... J'aimerais savoir où tu as trouvé ca...
29 nov. 2004 à 17:32
"il semble improbable qu'un nobre parfait soit impair"> ca ne veut pas dire impossible...
Je surenchéris : pi et les nombres premiers, comme e et la plupart des constantes irrationneles transcendantes sont ABSOLUMENT NECESSAIRES ne serait ce que pour connaitre avant de comprendre ce qui dépasse la logique humaine :p
Rien n'est inutile, de plus, et pi comme e comme les nombres premiers sont à la base de nos math modernes (cos, sin, racine et j'en passe) et bien que nous n'égalerons jamais nos (z) ainés rien n'empeche de suivre leurs traces, c'est peut etre d'ailleurs le meilleur moyen de les surpasser...
non ?
Vlad
28 nov. 2004 à 21:21
Pour trouver un nombre premier a 10 millions de chiffres, je vous souhaite bon courage. En effet, le M40 (a priori) ils ont mis 2 ans pour le trouver le programme GIMPS (celui de pingouin) et je pense qu'ils ont pas mal de tête et d'ordis la-bas :o) Donc ne revez pas trop non plus ;o)
28 nov. 2004 à 20:42
28 nov. 2004 à 20:40
28 nov. 2004 à 18:29
28 nov. 2004 à 18:20
Une question dans le meme style : a quoi ca sert de chercher ?
Cherchez et arretez de poser des questions
Vlad
28 nov. 2004 à 18:15
28 nov. 2004 à 16:37
évidemment, les exponentielles auto-réferentielles (n^n, e^e...) ne marche pas... mais toute suite a progression affine ou géométrique ont le meme effet
TT simplement : x mod 5 4 alors x-1 mod 5 3 ...
et x * 4 mod 5 = 1... ce qui ne change pas l'ordre mais juste le premier élément :)
Vlad
28 nov. 2004 à 16:32
1,4,2,1,0,1,3,1,4,0,1,1,...
mais effectivement puisque 2^p est une progression geometrique de raison 2, ca marche pour 2^p et si ca marche pour 2^p mod n et que (2^p-1) mod n = ((2^p mod n)-1 mod n) et ca marche aussi (les 0 de la serie deviendront n-1 et les autres seront diminuer de 1 mais la serie reste intact).
28 nov. 2004 à 14:51
Ca vaut pour tous les nombres ca, pas seulement pour les nombres de la forme 2^p-1 et pas seulementr pour les nombres premiers non plus :)
Vlad
28 nov. 2004 à 14:47
Pour compléter les nombres de mesrennes et leur lien avec des parfaits : le seul nombre premier, impair et parfait serait supérieur à 10^300 et contiendrait plus de 70 facteurs premiers et serait un nombre de mesrenne...
Bonne chance a celui qui le trouve...
Vlad
28 nov. 2004 à 14:43
Oui mais justement il doit y avoir moyen de sensiblement accéleree les calcul en tenant compte de la forme de 2^p-1
en fait je sais qu'un theoreme dit que si on prend des nombre en progression geometrique et qu'on prend leur modulo par un nombre premier p on tombe 1 fois sur tout les nombre entre 0 et p-1 avant de retomber sur un de cette série. ces pas facile à expliquer mais je sais qu'on utilise cette technique en dans le pour indexer des elements dans une liste.
comme j'ai dit plus haut :
mod 3 : 0 si n est pair 1 si impair donc c = p mod 2
mod 5 : si on prend p =1,2,3,... c une suite de 1,3,2,0, 1,3,2,0,....
(2^1-1) mod 5 = 1
(2^2-1) mod 5 = 3
(2^3-1) mod 5 = 2
(2^4-1) mod 5 = 0
(2^5-1) mod 5 = 1
(2^6-1) mod 5 = 3
...
je ne tien pas compte que p doit être premier ici mais ca doit etre pris en compte pour eliminer deja une partie des p
idem pour mod 7 : 1,3,0, 1,3,0,...
on doit peut être pouvoir demontrer a partir de ca que le modulo d'un nombre en 2^p -1 par un nombre premier nous donne une serie qui se repete en augmentant p de 1 a chaque fois.
pour mersene 41 c pas ca. ca veux dire que c'est le 41eme nombre de mersene premier.
non c'est pas mon site ^^.
28 nov. 2004 à 14:28
28 nov. 2004 à 14:26
28 nov. 2004 à 14:21
et alors (j'ai vu ça sur tes liens sibi12) quand on parle de Mersenne 41, ça veut dire que le nombre p est constitué de 41 "1" ?
28 nov. 2004 à 14:14
28 nov. 2004 à 14:10
28 nov. 2004 à 14:09
ou plus complet : http://membres.lycos.fr/villemingerard/Decompos/ParfDebu.htm
28 nov. 2004 à 13:48
1
11
111
11111
1111111
11111111111 (11, pas premier)
etc... :o)
28 nov. 2004 à 12:54
Et c'est quoi l'histoire des nombres parfaits ? c'est ceux qui s'écrivent sous la forme :
n=2^(p-1)*((2^p)-1) ??
28 nov. 2004 à 12:52
je viens de penser à un truc. si un nombre de mersenne est de la forme 2^p-1 on est pas obliger de le representer en mémoire puisque en base 2 une suite de p 1. il doit y avoire moyen d'extrapoler quelque chose de ça pour faire des modulo rapide...par ex :
(je fait les calculs en live :p)
mod 3 : 0 si n est pair 1 si impair donc c = p mod 2
mod 5 : si on prend p =1,2,3,... c une suite de 1,3,2,0, 1,3,2,0,....
mod 7 : 1,3,0, 1,3,0,...
en fait si on arrive à montrer que c'est tjs une suite suffit de cherche p mod premier_0_de_la_suite. si c'est 0 n n'est pas premier sinon on continue la boucle !!!
d'accord je l'accorde c'est pas super simple à coder mais on pourrait chercher mathematiquement avant de coder à la bourrin
28 nov. 2004 à 12:41
Ya un projet en ligne style Seti@Home qui fait ca http://mersenne.org/primenet si ca vous tente...
28 nov. 2004 à 12:30
28 nov. 2004 à 12:27
28 nov. 2004 à 12:19
27 nov. 2004 à 20:41
Oui le C est le mieux mais c'est possible de tout codé en VB. Je te conseille alors d'utiliser la bibliotheque NTL et dans cet lib le type ZZ. http://shoup.net/ntl/
27 nov. 2004 à 20:34
Pour les longs chiffres, je vais tenter une petite classe en C, ca me parait beaucoup plus pratique :o)
27 nov. 2004 à 20:10
Oui oui je sais mais c'est encore plus difficile de trouver un nombre parfait surtout que le nombre parfait correspondant à 2^p - 1 est 2^(p-1)*((2^p)-1) et est donc encore plus grand (+- égale au carré).
Je viens de faire le calcul pour le fun pour un nombre parfait de la forme n=2^(p-1)*((2^p)-1), M=sqrt(n+1)-1
Niveau rapidité utilise la base 2 l'addition la soustraction et la multiplication sont vraiment triviale la division et le modulo doivent resté raisonnable. je commence à être tenté.
en fait le modulo et la division se complique quand le les operande n'ont pas le même ordre de grandeur mais en tapant ça dans une boucle c'est pas la mort.
27 nov. 2004 à 19:57
et tous les nombres de Mersenne ne sont pas premiers : M11 ne l'est pas.
Volia...
27 nov. 2004 à 19:46
27 nov. 2004 à 18:57
Par contre si p est premier la oui je ne dis pas. Par contre tu as sans doute vu sur ce site que si on a un nombre de Mersenne on en a immédiatement un parfait !! Kan est ce que ce code (qui recueille un sacré paquet de commentaires kanm^m!!) détectera les nombres de Mersenne ?
27 nov. 2004 à 16:36
les nombres de mersenne sont les M qui sont premier mais le theoreme ne dit pas que la reciproque est vraie.
27 nov. 2004 à 16:34
le theorme dit :
M = 2^p - 1
Si M est premier
alors p est premier
http://membres.lycos.fr/villemingerard/Premier/record.htm#Mersenne
27 nov. 2004 à 16:19
Mindiell> ce que je voulais dire c que tous les nbx de Mersenne ne sont pas premiers (n=4 si je ne dis pas de betises ) et que tous les nombres premiers ne sont pas des nombres de Mersenne (17 par exemple non ?) Bref.
Dis si Madmatt gagne le fameux prix 'croyez kil va partager comme il partage ses sources ? ;Þ
27 nov. 2004 à 15:31
Et celui dont je parlais vaut ca : 2^24 036 583 -1
Oui, oui, 2 puissance 24 millions :o)
27 nov. 2004 à 15:26
2^24 036 583 -1 (oui il y a un problème 240 36 583 c'est pas 240 millions)
MadMatt > La base 2 est tellement plus simple le seul problème est le passage en string mais ce n'est pas si compliquer que ça n'y parrait, suffit de jouer avec des mod 10 et int(n/10).
Passé à 2 nombre par caractère ne va pas tant complexifier le code tu va devoir chaque fois passé par un Int(Asc(Mid(var,i,1)) / 10) ou Asc(Mid(var,i,1)) mod 10 et puis par Chr(10*N1+N2) puis convertir en string.
tu peux pas me dire de quel source tu partirais pour gerer tes nombres ?
27 nov. 2004 à 13:25
MadM@tt >> Si tu arrives a construire un ensemble de fonctions mathematiques de ce type moi je m'emballe. Ce qui est dommage c'est que je ne suis pas sur d'avoir le temps suffisant pour te proposer mon aide mais on ne sait jms donc si tu as besoin n'hésites pas...
bon courage
Pingouin
27 nov. 2004 à 11:52
Seulement je me disais, un octet peut stocker 256 valeures (avec le 0 ça fait 255), alors pourquoi utiliser que 10. ça serait mieux de faire des fonctions dont l'octet stocke 2 chiffres non ? donc de 00 à 99
comme ça ça diminue de moitié l'espace de stockage ?
par contre la ou ça serait difficile c'est au niveau des calculs pour incrémenter à chaque fois d'un.
remarque ça doit etre faisable
27 nov. 2004 à 05:05
Ces fameux chiffres énormes sont des nombres de Mersenne, donc pour les stocker pas besoin de grand chose :) ca donne ca : Mn = 2n - 1 (comprendre 2 puissance n), il suffit donc de connaitre n. Malheureusement ils ne sont pas tous premiers :o)
26 nov. 2004 à 21:46
10 millions de chiffres ça fait rever quand meme....
ça devient plus tentant l'histoire des grands nombres, je me lancerai bien dedans pour voir.... Si ce week end j'ai le temps, j'étudierai la question, en tout cas je ne mettrai pas la source à jour ici mais j'en posterai une nouvelle car les sources n'auront rien à voir (encore faut-il que j'y arrive)
sinon merci à vous tous pour vos commentaires.
faites chauffer le clavier...
@ +
26 nov. 2004 à 19:55
ui C/C++ idem ;-)
J'avais déjà entendu parler de ca. ca fait qd même 33Mo rien que pour stocker le nombre !! mais il y a des technique beaucoup plus sofistiquer style champ de mersene et tout ca...
26 nov. 2004 à 17:25
un tableau d'octets surtout ! donc comme une chaine de caracteres, mais pas un type String. En effet, le C est mieux pour ca (pas forcement besoin du C++)
Pour les nombres premiers, le record est aux alentours de 7 millions de chiffres. L'EFF offre 100 000 dollars au premier découvreur d'un nombre premier à 10 millions de chiffres... Sur ce, bon courage ;o)
26 nov. 2004 à 17:14
25 nov. 2004 à 20:44
25 nov. 2004 à 20:19
Et pourquoi pas proposer une option pour ne stocker kun certain nombre, parmi les derniers...
Sinon je ne suis pas un spécialiste mais vous croyez qu'il y a moyen de travailler sur des strings pour s'affranchir de la limite de taille des long ? Mais c sur ke la il te faudrait faire toi meme les opérations .... C'est ptet a voir non ?
25 nov. 2004 à 17:44
Pour le problème des fichiers je n'ai pas le courage de développer un truc entier rien que pour les ouvrir, je pense que la solution de Mindiell est pas mal, dans un sous-dossier
Je vais voir ça, mais je pense faire avec les Mo, c'est à dire que je pourrai faire 2Mo par 2Mo, ça évite les mauvaises surprises et le programme sera plus simple
merci pour les idées
25 nov. 2004 à 00:27
25 nov. 2004 à 00:08
Comme le signale dnob700, c'est inutile car tu recuperes nimporte quoi. Le double en 64 bits ne garde de precision que sur une plage de 20 chiffres maxi, au dela on entre en virgule flottante a 'double IMprecision', alors tout ceci est totalement inutile.
25 nov. 2004 à 00:01
24 nov. 2004 à 23:49
Tu peux ensuite lire le fichier on ne peux plus simplement en chargeant les donnée dans un tableau de long.
de toute maniere tu va avoir du mal pour gerer des nombre à plus de 32 bit en VB.
l'ennui est si tu vx qd même gerer ces nombres
24 nov. 2004 à 22:35
24 nov. 2004 à 22:25
Voila une idee qui te fait deja gagner 1 octet par nombre ecrit dans le fichier (je fais cas ou tes nombres ne sont pas plus grands que 255 caracteres), il faut indexer en ecrivant 1 octet devant chaque nbr (en binaire brut) indiquant sa longueur et ecrire tout a la suite sans saut de ligne. A la lecture on sait exact ou aller chercher le prochain et on peut donc y pointer direct.
Ensuite bien sur aucune idee comment transcrire cela en VB, a vous de voir. Pour autant c'est je pense ainsi que je ferais en C et devrait etre tres rapide.
24 nov. 2004 à 21:33
24 nov. 2004 à 21:26
http://www.bibmath.net/dico/index.php3?action=rub&quoi=603
Pour créer ou vérifier (probalistiquement) un nombre premier :
http://www.bibmath.net/crypto/complements/gdspremiers.php3
MadM@tt > comment vas-tu faire pour regarder dans un fichier texte decette taille-là alors ?
24 nov. 2004 à 18:22
Comme quoi au bout d'un moment tout tes résultats, il ne vaut mieux pas avoir envie de les voir tous d'un coup :(
24 nov. 2004 à 17:51
24 nov. 2004 à 17:26
Mindiell > Tu aimerais un programme qui travaille et que tu ne puisse pas voir le résultat, enfin c'est vrai que je pourrai ajouter une option pour cacher ou pas la liste, je vais étudier ça
zoslex > Comme je viens de le dire, je vais donc ajouter l'option pour cacher ou montrer la liste, comme ça si on laisse tourner le prog pendant 1h quand on est pas la, autant cacher la liste, et si on veut on pourra la voir
Sinon pour ta question à propos du nombre 99 999, la réponse est simple :
c'est un nombre pris au hasard, ni trop grand ni trop petit, je m'explique. Au départ le programme calculait comme un fou et mettait tout dans la listbox, et il sauvegardait quand on l'arretai. Sauf que si ton ordi plantait tes progrès étaient effacés, et au bout d'un moment ça commence à prendre de la place en mémoire, ce qui peut ralentir encore + le programme (et en + au moins tu voit l'avancement, alors qu'avant tu ne voyais pas apparaitre les nouveau nombres).
C'est pourquoi tous les 99 999 nombres, tout est rafraichit, on avance par étape en fait, et bien sur ce nombre peut etre changé, je l'ai pris pour pas que le rafraichissement soit trop fréquent, ni trop espacé.
voilà
24 nov. 2004 à 14:29
- Si on calcule 150 Millions de nombres premiers, quel est l'intérêt de les afficher ?
24 nov. 2004 à 14:23
Je m'explique... Je suis arrivé aux alentours de 150 000 000 avec un fichier de 92 Mo. Le temps est en deux parties : le calcul et la sauvegarde.
- Le calcul avec mise dans la liste : la cacher avec Me.Liste.Visible donne 40% de gain (6s au lieu de 10s).
- La sauvegarde : ça me prend 35s de faire Save.
Alors, avec autant de temps pris pour la mise sur disque dur par rapport au calcul à proprement parler, je me demandais le pourquoi du 99 999.
Ne peut-on pas augmenter ce nombre ? Quelle est sa limite ?
23 nov. 2004 à 22:24
23 nov. 2004 à 22:08
Vlad > Je vais tester avec LockWindowUpdate
dnob700 > merci pour tes pdf je vais y faire un tour
vous savez que tout les soirs ma boite hotmail est prete à exploser avec tous les commentaires que vous envoyez... 20 mails par ci, 15 par la
Mais continuez !!! On avance !
@ + tous
23 nov. 2004 à 22:00
mais il te faut plusieurs essais avant de trouver de ton y. alors qu'avec erathosthene tu trouve toute une volée d'x d'un seul coup l'ennui est que parfois il sont deja cocher. enfin j'ai jms trop aimé erathosthene et j'ai jms fait de test mais jme suis tjs di ke ça devait etre plus rapide... têtre que je me trompe.. je n'en sais rien.
"Quant aux compilations, les vitesses dépendent tant de la machine que du programme que de la méthode que du moment"
Je vois pas où tu veux en venir.. même si je reconnais que ce sera jms aussi rapide que du C++ (quoique en theorie ça devrait après la première compilation mais je me suis vite rendu compte du contraire), ça n'equivaut quand même pas à du VB vu la lourdeur des appels de fonction.
23 nov. 2004 à 20:07
ce qui n'est par le cas du C++ compilé pour win32 (faites l'essai, je ne veut pas lancer de polémique, mais c'est vraiment plus rapide).
pour ce qui est des nombres premiers, il y a ces deux pdf qui sont très bon si vous êtes un peu interessé par de la théorie :
http://perso.wanadoo.fr/sectionpc/tpe_cryptage/crypto/pdfs/primalite.pdf (en français)
http://perso.wanadoo.fr/sectionpc/tpe_cryptage/crypto/pdfs/primality.pdf (en anglais)
23 nov. 2004 à 19:28
Chercher tous les nombres premiers de 1 à n... c'est exactement ce que fait ce programme
Maintenant, la méthode du crible d'eratostene consiste a barrer tous les éléments d'un tableau périodiquement (a savoir par exemple, tous les multiples de 17) ce qui revient mathématiquement à un modulo, qui est, de plus très rapide.
Si x mod y = 0, alors x est un multiple de y , donc on le barre car un premier ne peut etre un multiple :)
Quant aux compilations, les vitesses dépendent tant de la machine que du programme que de la méthode que du moment
Si c'est pas flagremment différent, considère que c'est pareil
Vlad
23 nov. 2004 à 19:24
je me disai la même chose du CLR au debut mais en y regardant de plus près le jit fais qu'on a un code plus ou moins aussi rapide que du C++. l'idéal pour le verifier serai de faire un sgen sur un prog .Net et voir
23 nov. 2004 à 19:03
De plus, il a parfaitement raison de dire que le CLR compile des programmes a peu près aussi rapides que VB6
MadMatt & zoslex> Encore mieux : essayez l'api LockWindowUpdate :)
LockWindowUpdate list1.hWnd
'remplissage
...
LockWindowUpdate 0
list1.Refresh
Evidemment, il faut faire
LockWindowUpdate 0
list1.Refresh
de temps en temps (exemple tous les 10000 éléments ajoutés) pour que ton prog ne plante pas
Vlad
23 nov. 2004 à 17:29
Le gain est largment visible... Je pense que la perte est constante puisque dû à la perte de temps d'afficher en permanence.
Ce que j'ai changé :
' Procédure qui cherche les nombres premiers
Private Function CherchePremier()
Dim Number As Double
'zoslex
Me.Liste.Visible = False
Me.Caption = "Recherche ... - MadMatt"
puis à la fin de la fonction :
Me.Caption = "Fini !"
'zoslex
Me.Liste.Visible = True
End Function
Merci de dire si tu vois mieux, ou si tu ne vois toujours rien.
Préviens si tu mets à jour, que je télécharge la dernière version, merci :)
23 nov. 2004 à 16:20
tu prend le premier nombre premier c a d 2 (mais on peux aisément le sauter pour gagner en performance) et tu fais plus 2 et tu coche le nombre obtenu c a d 4 puis 4 + 2 et tu coche dc le 6 tu continue juske n ensuite tu prends le premier nombre qui n'est pas cocher c a d 3 tu fait + 3 tu coche le 6 (il est deja cocher d'ou l'interet de sauter le 2 : cfr dnob700 : "En parcourant le tableau de 3 en 3, tu passe les nombre de six en six, mais c'est pas grave puice que un sur deux est pair")
Il n'y a donc aucun modulo/division même pas une simple multiplication !!!sachant qu'une addition s'effectue en 1 cycle comme toute les autres instruction de l'algorithme (mise à part les accès memoire qui eux sont plutôt fréquent. on doit charger 4 octet tout les 64 nombre si le programme est bien optimiser) on comprend pourquoi il est si rapide.
dnob700 > Le CLR et le run-time VB n'ont absolument rien en commun ! Tu te trompes. Le CLR prend du code CIL et le traduit en code machine, avec une aussi bonne optimisation que du C++ (pour autant que le programme soit bien écrit), lors de la première exécution d'une fonction, ensuite la fonction est stockée en langage machine et s'exécute comme une application normale (en gros).
En VB c'est complètement différent t'as ton programme en langage machine mais 9 instructions sur 10 font appelle a une dll ce qui ralenti sensiblement ton code surtout que beaucoup d'appelle utilise le protocole COM dont la lenteur des appels de fonction est bien réputé. et même pour les appel qui n'utilise pas COM, passé les arguments sur la pile pour faire une addition n'est pas skon peux trouver de mieux niveau performance.
Je ne pense donc pas qu'on puisse dire que VB soit plus rapide qu'un programme .Net à part peut-être au premier appel de la fonction (au besoin on peut utiliser sgen il me semble pour compiler le CIL en langage machine)
23 nov. 2004 à 00:16
MadM@tt, en effet, ne pas utiliser ta liste de gauche accélère de beaucoup le calcul quand tu en fais un long...A priori, ca le fait même planter au bout d'un moment (Textbox trop petite...)
23 nov. 2004 à 00:06
je suis allé jusqu'à un nombre qui s'écrit avec 8 chiffres, dans les 500 000 000 (500 millions) c'est pas mal non ?
mais ça reste bien loin des supercalculateurs
23 nov. 2004 à 00:05
J'ai essayé plusieurs méthode pour stocker les resultats dans une chaine de caractère, un tableau, mais pas de changement de vitesse significatif.... à moins que j'ai mal compris ce que tu voulais dire....
mais merci d'avoir proposé l'idée quand meme
@ +
22 nov. 2004 à 23:27
le C# est compilé pour la CLR, c'est a dire exactement la même chose que du VB (donc il a la même vitesse, d'ailleur de VB.NET est un peu plus lent que du VB6).
Par contre, du vrai C++, compilé pour win32 (ou linux) est plusieurs centaines (peut être seulement plusieurs dizaine, c'est assez dificile de faire des test précis car ça n'a pas grand chose à voir) de fois plus rapide peut-être.
22 nov. 2004 à 22:46
il est surtout plus rapide car on ne fait aucune division et 5 6 addition seront tjs plus rapide que 1 modulo(le modulo a la meme instruction machine que la division)"
Eratostene consiste a éliminer les nombres en fonctions des modulos, pas en fonction des additions... on ne fait pas d'additions me semble-t-il
Enfin si ma mémoire n'est pas encore totalement décrépie...
Vlad
22 nov. 2004 à 22:37
il est surtout plus rapide car on ne fait aucune division et 5 6 addition seront tjs plus rapide que 1 modulo(le modulo a la meme instruction machine que la division) il y aussi quelque rotation pour implementer le tableau decrit par dnob700 mais c'est 1 cycle aussi comme l'addition.
sinon si c'est juste pour verifier un nombre ca vaut pas la peine (une idée sur le moment coupler erathostene avec la methode classique : on fait un tableau de sqrt(n)/2 bits et avant de mettre à un les nombre non premier on verifie si il est diviseur de n... à creuser mais fort limité)
MadM@tt > logiquement C# et C++ devrait etre aussi rapide l'un que l'autre mais je n'en suis pas convaincu. l'ennui du C# est qu'il y a plein de truc qu'on ne contrôle pas comme la memoire, le garbage collector peux se declencher à n'importe quel moment, il faut passer en mode non proteger pour gere les pointeurs,... je pense qu'il vaux mieu faire en C++ et au besoin appeler une Dll d'un programme C#
22 nov. 2004 à 21:58
Mais le problème des grands nombres reste encore je vais essayer de regarder ça si je trouve du temps
22 nov. 2004 à 21:50
Vlad :)
22 nov. 2004 à 21:48
zoslex > yes bonne idée, vu le gain de temps je vais vite mettre ça au point
Pour les autres à propos des grands nombres j'ai encore jamais regardé mais je me pencherai bien dessus
Sinon au niveau du crible d'erastosthene et patati et patata vous etes sur que ça peut permettre de gagner du temps ? Parce que ça a l'air compliqué et pour moi qui dit compliqué du beaucoup de calculs donc un temps long, enfin je dit ça sans avoir jamais testé quoi....
sinon merci à tous pour vos commentaires
PS : j'essayerai bien de mettre cette source en C++ ou C#, mais est ce que le C# est aussi rapide que le C++ ?
22 nov. 2004 à 18:56
Par contre a mon avis le crible c'est pas la peine a mon avis c'est pas efficace pour de grands nombres.
Mais au fait tant qu'il y est ya moyen d'etendre le prog a la factorisation en facteurs premiers non ? :-) (histoire d'élargir le débat ... koike 36 commentaires c deja pas mal lol)
Pingouin
22 nov. 2004 à 18:29
22 nov. 2004 à 18:27
Le crible d'Eratostène consiste a préparer un tableau et a éliminer les nombres en fonction des Modulo ... ce qui revient a faire le code "brutal" que l'on avait au début, a savoir
For I = 0 to sqr(x)
If x mod I = 0 then x pas premier
...
Maintenant, pour le stock, il faut prendre en compte que si le but du code n'est que de décorer... autant ne pas se trouer les méninges... maintenant si tu veux que ca soit utile, tu peux adapter ton code pour des recherches sur les très très grands nombres premiers (sans me faire de la pub, j'ai fais un module qui permet de gérer de tels entiers et que tu pourrais utiliser assez facilement)
Accélérer la recherche au dela me semble difficile, au vu des limitations (pratiques) de VB...
Mais je ne doute pas que qqn y arrive quand meme :)
Vlad
22 nov. 2004 à 18:22
Ceci dit, le crible d'erathostene m'intrigue, je vais me pencher dessus :)
22 nov. 2004 à 18:20
sauf a savoir si 86 125 647 est un nombre premier sans calculer les autres, là, ça sers à rien.
22 nov. 2004 à 18:18
22 nov. 2004 à 18:15
de toute façons, à moins de compressé à la volée c'est la meilleure méthode pour sauvegarder les premier nombre premier (jusqu'a 100 milliosn c'est que les premier) après, quand leur consistance devient trop faible il faut envisager autre chose.
mais un tableau de double, dynamique qui plus est, est vraiment une abération (dans la même mémoire on ne mets même pas 2 millions de nombre premier).
22 nov. 2004 à 18:01
Par contre, pour tester si un grand nombre est premier ou pas, ca marche plus du tout (ou alors faut y aller)...
22 nov. 2004 à 17:53
disons que le premier bit vaut 3.
tu parcours donc le tableau de 3 en 3 en mettant tout les octets à zéro (il faut qu'avant ça, tout est été initialisé à 1 ou le contraire).
En parcourant le tableau de 3 en 3, tu passe les nombre de six en six, mais c'est pas grave puice que un sur deux est pair.
quand c'est fini (c'est a dire quand t'arrive au bout de ton tableau).
tu rapars du début et tu cherche le premier éléments qui soit à 1.
ici, ça sera le deuxième, alors tu recherche sa valeur (pour l'élément x (le premier est 1et non pas 0) c'est (x*2+1)) et tu pacours le tableau de x*2+1 en x*2+1 donc là de 5 en 5, mettant tout à 0.
et on recommence, tu cheche le premier qui soit à 1 et tu mets à zéro tout ces multiple.
à la fin, il ne te reste à un que les nombre premier.
avec cette méthode j'ai calculé les 100 000 000 premier nombre premier non pas un 2 jours mais en 2 minutes a peu près (bon, avec un noyau pour la manipulation du tableau en C, mais même en pure VB, ça sera bcp plus rapide).
22 nov. 2004 à 17:42
Le problème, c'est que s'il veut diviser rapidement son nombre a tester par les 100 premiers "nombres premiers", il doit les retrouver, non ? L'avantage du tableau "horrible" c'est qu'il contient les 100 premiers :o)
Pour Erathostene, tu pourrais mieux expliquer ? J'ai pas le temps de faire de recherche, mais j'aimerais comprendre le truc quand meme ;o)
22 nov. 2004 à 17:18
Ca sers à rien d'utiliser des double parce qu'il ont 12 ou 13 chiffre de précision mais au delà, tout est perdu et le calculs que tu fait n'ont plus de signification.
Donc il faut le faire avec des long, mais tant que tu ne gère pas de nombres plus grand que la limite des long, on peut dire que tu gère des "petits" nombres.
donc une méthode très rapide pour faire le calcul est tout simplement le crible d'érathostène, tu cré un tableau pour stocker tes nombre, mais pas un tableau horrible comme on te l'a conseillé plus haut, juste un tableau de byte ou chaque bit représente un nombre :
e premier est 3, le 2ième est 5 et ainsi de suite tout les nombre impair sauf 1.
bon, et ensuite, je suppos eque tu conait le principe du crible d'érathostène (tu coche tout les nombre multiple de nombre premer et à la fin, ce qu'il reste est les nombre premier.
22 nov. 2004 à 16:01
J'ai fait un programme du style il y a quelque temps mais je ne le retrouve plus j'ai du l'effacer lors du gd nettoyage :(...
Sinon pour l'idée du tableau je l'avais implémenter, ça prens pas mal de place en mémoire mais le gain de temps est interressant. Pour repondre à ta question avec les grand nombre, si tu t'ai déjà interesser à la représentation en memoire tu devrai savoir qu'un entier sous VB est codé sur 32 bit et est signé. la plage est donc de -2^31 à 2^31-1.
La fpu (floating point unit ou coprocesseur arthmetique) permet de jouer avec des entiers sur 64 bit et qui ont dc une plage si on compte seulement les positif jusque 2^64-1 soit +- 1.8 * 10^19. Le problème est que VB n'implémente qu'une version modifier : le Currency. il décale la valeur de 10 000. je ne sais plus si cette implemantation est signée ou non mais son max ne depassera de toute facon pas 1.8*10^15 et tu va perdre pas mal de temps.
Si tu veux quelque chose efficace pour un eventuelle RSA je te conseille de te tourner vers le C++ et d'utiliser sa librairie ZZ (une tite recherche sur google pour la trouver).
Pour l'algo des 3 indiens c'est utile uniquement pour les très grand nombre et n'est pas trivial a implémenter. la premiere condition à vérifier est que le nombre ne peux pas s'écrire sous la forme n=a^b ou un truc du style.
Il y a un autre algo fort utiliser pour le RSA c'est Miller-Rabin qui se base sur des nombre aléatoire mais il ne donne qu'une probabilité si le nombre est premier. Si le test dit que le nombre n'est pas premier c sur a 100% sinon la probabilité qu'il ne soit pas premier est de 1/4. en repetant le test n fois la probabilité sera de (1/4)^n. on peux donc être amplement satisfait après une 20aine de test (1 chance sur 4^20 soit 1 sur +- 10^12)
voilà si t'as des question je m'etait pas mal renseigner sur les nombre premiers. Le plus rapide est sans doute Erathostene mais inaplicable sur des grand nombre.
22 nov. 2004 à 11:13
Mais si tu cherches la rapidité, un truc qui accélère vachement : ne pas afficher la liste.
Quand ça tourne, mets
Me.Liste.Visible = False
puis quand ça s'arrête, tu reviens à
Me.Liste.Visible = True
Jusqu'à 170 000, je passe de 15s à 3s.
Continue, tu tiens le bon bout.
20 nov. 2004 à 22:23
Un nombre, si il n'est pas premier possède au moins un couple de multiples comme celui ci
a*b
avec a>b et a <> 0, alors il possède aussi comme multiple le couple :
b*a
Il faut donc s'arrêter à la racine carrée : quand a=b; toutes les recherches après sont vaines :).
20 nov. 2004 à 11:49
je vais y regarder merci
20 nov. 2004 à 02:18
20 nov. 2004 à 00:09
à chaque lanvement du prog il faut charger tous les nombres premiers déjà trouvés (par exemple la je le laisse tourner de temps en temps depuis 2 jours et j'en suis à 100 000 000 ce qui me fait un fichier de sauvegarde de 70 Mo et donc va charger ça en mémoire)
et il faut être sur d'avoir non seulement des nombres vraiments premier mais je pense que l'algorithme ici est bon et aussi avoir trouvé TOUS les nombres premiers avant celui que tu cherche, donc on ne peut pas commencer arbitrairement à une valeur, on est obligé de démarrer de 1 lors de la première utilisation...
Enfin ça fait pas mal de problème pour, je pense, un gain de temps pas énorme
19 nov. 2004 à 22:47
For I = 0 to int(sqr(ubound(prems)))+1 <= inutile et innefficace - tu comprends je crois que prems contient les nombres premiers trouvés (exemple prems(4) = 13 ) et que j'avais déjà pensé a mettre "If prems(I)<int(sqr(x)) then" une ligne en dessous :)
Bien essayé :)
Par contre, Pingouin : la formule de Ramanujan permet de tester la primalité de nombres de plusieurs millions de chiffres (binaires) en quelques secondes :) donc plus lent c'est discutable :)
Vlad
19 nov. 2004 à 21:09
Vlad2i > excellente idée, ça évite de rediviser à chaque fois par tous les nombres meme ceux pas premier. Et dans la meme logique, autant essayer de diviser par tous les nombres premiers jusqu'a la racine du nombre à tester, ce qui donne :
Function TestPremier(x)
If X mod 2 = 0 then PasPremier
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' Le changement est ici
For I = 0 to int(sqr(ubound(prems)))+1
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
If prems(I) si j'ai bien fait la relation tu doit parler des meme bonhomme que parlait Vlad2i plus haut, avec l'intégrale de ramanujan, si tu trouve quelque chose ça peut etre pas mal
merci à vous pour vos commentaire, j'essayerai de modifier la source ce soir
@ +
19 nov. 2004 à 19:34
Ben ecoute ca fait plaisir de servir a quelque chose de temps a autres.
Sinon je vois que ca a pas mal progressé depuis mon dernier passage !! En effet quelques tests préliminaires ne sont pas a négligés surtout pour de grands nombres. Encore quelques secondes de gagnées !
Sinon je vais essayer de voir si je le retrouve mais il serait intéressant d'implémanter le dernier algorithme a ce sujet qui nous vient de deux mathématiciens indiens qui parait il est une preuve mathématik mais pas forcement bcp plus rapide voire plus lent d'apres ce que j'ai entendu dire. si kkun voit de koi je veux parler kil n'hésite pas...
Voila voila,
Bonne continuation j'essaierais de garder un oeil la dessus ca m'interesse.
19 nov. 2004 à 16:57
19 nov. 2004 à 16:46
Function TestPremier(x)
If X mod 2 = 0 then PasPremier
For I = 0 to ubound(prems)
If prems(I)<int(sqr(x)) then
If X mod Prems(I) = 0 then
PasPremier
Exit Function
Endif
endif
next
Premier
redim preserve prems(ubound(prems)+1)
prems(ubound(prems)) = X
End Function
Par exemple :)
Vlad
19 nov. 2004 à 16:38
Quant à 1 il n'est pas premier :) l'algo est donc sûr au delà de 5 inclus :)
19 nov. 2004 à 16:33
1
5
7
Je suis au regret de te dire qu'il manque 2 et 3 comme nombres premiers. J'accorde le 1 bien qu'au point de vue mathématiques le 1 n'est pas premier pour des questions de généralisation de lois sur ces nombres...
18 nov. 2004 à 22:27
j'ai essayer de détecter si c'était un nombre pair ou multiple de 5 avant les calculs plus compliqués mais j'ai constaté aucun gain de temps, si ce n'est de la perte.
Pour ton truc de modulo, ça m'a fait gagné environ 1 sec sur 13 c'est pas mal, j'ai donc environ 12 sec pour 100 000 nombres premiers trouvés
merci vlad
(je met la source à jour)
18 nov. 2004 à 22:20
If ((x mod 4 3 or x mod 4 1) and (x mod 6 = 1 or x mod 6 = 5)) Then
'La tu teste la primalité - la nombre est peut etre premier
else
'Le nombre n'est pas premier
endif
Car il se peut qu'un nombre ne soit pas premier mais passe le test qd meme, et là tu peux d'office tester (ce qui réduit considérablement les tests qd meme)
"quand tu parle de 100% de certitude, tu veux dire que l'algorithme (barbare c'est clair) que j'utilise n'est pas très fiable ?"
Non, en fait il est fiable, mais lent - je parlait de l'algorithme intégral, enfin peu importe
Vlad
18 nov. 2004 à 22:14
Comme tu l'a dit il faudra penser au grands nombres, et pour les techniques que tu m'a donné pour calculer plus vite les nombres premiers merci beaucoup je regarderais ça avec bcp d'attention.
mais par contre je ne comprend pas pourquoi tu veux faire une boucle de I à I/6, c'est pas possible de tester ça ? :
If (x mod 4 3 or x mod 4 1) and (x mod 6 = 1 or x mod 6 = 5) Then
quand tu parle de 100% de certitude, tu veux dire que l'algorithme (barbare c'est clair) que j'utilise n'est pas très fiable ?
Et enfin oui je vais penser à détecter automatiquement les chiffres pairs.
merci
@ +
18 nov. 2004 à 22:05
Quelques idées :
Un nombre premier x est forcément tel que x mod 4 3 ou x mod 4 1 et forcément tel que x mod 6 = 1 ou x mod 6 = 5 ca peut largement augmenter la vitesse de ta recherche (par exemple en fesant une boucle de I à I\6 et en testant la primalité des nombres 6*I+1 et 6*I-1)
Ensuite, éviter les nombres évidemment pairs, alias nombres pairs et multiples de 5 par exemple ...
Si tu veux vraiment un algorithme éfficace, j'ai un document de trois chercheurs indiens qui ont utilisé une intégrale de ramanujan pour étudier la congruence des nombres non premiers - et qui que quand il renvoie q'un nombre est premier c'est avec 100% de certitude (l'inverse n'est pas vrai par contre :))
Parce que pour RSA, la sécurité est faible en dessous de 300 chiffres, produit : 300×300 = 90000 chiffres pour le produit pq :) il faut donc que tu gères les grands chiffres :)
Vlad
18 nov. 2004 à 21:52
Pas mal non ?
18 nov. 2004 à 20:24
par contre je me demande si quand j'arriverai à des nombres tellement grands qu'ils seront stockés sous la forme .....*10^n
est ce que ça me garde en mémoire tous les chiffres du nombre ou alors ça garde seulement l'expression ....*10^n ? si quelqu'un peut m'apporter une réponse
18 nov. 2004 à 20:18
@ +
18 nov. 2004 à 19:59
Juste une petite amélioration de rien : j'ai vu que tu cherchais les diviseurs jusqu'a nombre /2 en fait on peut démontrer (mais c pas évident) qu'il suffit de s'arrêter a la racine carré du nombre, ca diminue sensiblement le nombre de calculs et améliore donc la vitesse, ce qui n'est pas négligeable dans ce genre de prog.
Sinon fais en quelque chose de bo graphiquement comme ca ca pourra en effet décorer le pc pdt kil ne fait rien...
@+
Pingouin
18 nov. 2004 à 19:35
18 nov. 2004 à 18:52
quand tu prend 2 nombres premiers p et q (qui je le précise ne sont donc divisibles que par 1 ou par eux-meme) et que tu les multiplie : p*q
le produit p*q peut-etre rendu public et des fichiers peuvent etre codés avec, mais pour décoder il faudra se servir de p et q séparément.
Or l'avantage des nombres premiers multipliés ainsi, c'est que à partir du produit p*q il est extremement difficile de retrouver le p et le q du départ... (ça nécessite énormément d'ordis et de temps).
Donc en gros tu code avec p*q qui est public, et seulement l'utilisateur qui a la vraie clé : p et q séparément, peut décoder le fichier obligatoirement avec les 2 nombres séparés (c'est du à des calculs mathématiques assez compliqués)
euh chu pas un expert, jme suis peut etre trompé quelque part mais dans l'ensemble c'est ça
18 nov. 2004 à 18:26
18 nov. 2004 à 18:14
pour ceux que ça interesse des scientifiques en ont trouvé à x10^340 chiffres je crois, dans cet ordre de grandeur la
Si vous avez un meilleur algorithme a proposer, allez-y