A SUPPRIMER
econs
Messages postés
4030
Date d'inscription
mardi 13 mai 2003
Statut
Membre
Dernière intervention
23 décembre 2008
-
2 mai 2005 à 08:59
cs_drache Messages postés 5 Date d'inscription vendredi 1 avril 2005 Statut Membre Dernière intervention 9 novembre 2005 - 9 nov. 2005 à 15:08
cs_drache Messages postés 5 Date d'inscription vendredi 1 avril 2005 Statut Membre Dernière intervention 9 novembre 2005 - 9 nov. 2005 à 15:08
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/31121-a-supprimer
https://codes-sources.commentcamarche.net/source/31121-a-supprimer
9 nov. 2005 à 15:08
8 nov. 2005 à 22:53
Ce que tu évoques est intéressant. Faire un programme pour étudier l'expression de Fermat est une bonne idée... mais maintenant par rapport à mon code de recherche de nombre premier, c'est un peu éloigné, même si on cause toujours de nb premier... Je t'invite (et d'encourage) à te lancer à l'eau en postant une version du code que tu proposes... et donc te soumettre aux remarques (espéront "constructives")...
Euh... je dis aussi cela, car je ne vois pas que tu as déjà déposé de source... Quant aux tournures de phrase, ça va très bien... juste p'être les fautes ... mais je ne suis pas trop au top non plus...
Amicalement,
Us.
8 nov. 2005 à 12:48
je ne m'etai pas aperçut qu'elle etait si mauvaise
7 nov. 2005 à 21:04
la limite de mod et de 2147483647
cad 2147483647 mod 2 (ou un peu plus je sai plus) par exemple est en probleme de capacitée
je l'ai remplacé par ((nbr / d) - Int(nbr / d)) * d = 0 qui meme si la formule est plus longue elle a un grand interét pour les grand nombres(limité au bout de un peut plus de 1,34078079299426E+154)
je l'ais utiliser pour ce code qui est cette formule :2^(2^n)+1 que fermat décreta ne donner que des nombres premier car il n'a put aller que jusqu'a n=5 pour l'époque(ce qui incroyable!!!)
et que toujour un ab***ti de mathematicien dise que pour n=6 sa marché plus(2 siecle aprés tout de meme!)
nous avons vu que jusqu'a n=20 cetai pas des nombres premier mais que aprés si
je suis arrivé a n=9 avant le depassement de capacité
je pense que pour parvenir a 20 je doit passer en compilateur (et encore!!)
voila le code:
Sub fermat1()
Dim debut As Date
Dim fin As Date
Dim Duree As Date
Dim n As Integer
Dim d As Variant
Dim premier As Integer
Dim p As Integer
Dim l As Integer
Dim Max As Variant
Dim compteur As Integer
Max = Cells(2, 2)
debut = Time
p = 6
l = 6
compteur = 0
For n = 2 To Max
'f = (2 ^ (2 ^ n)) + 1
compteur = compteur + 1
premier = 1
For d = 2 To (n ^ 0.5)
If ((((2 ^ (2 ^ n)) + 1) / d) - Int(((2 ^ (2 ^ n)) + 1) / d)) * d = 0 Then
premier = 0
Exit For
End If
Next d
If premier = 1 Then
Cells(p, 1) = n
p = p + 1
ElseIf premier = 0 Then
Cells(l, 2) = n
l = l + 1
End If
Next n
Cells(2, 3) = "nbr de solutions " & (p - 6)
fin = Time
Duree = fin - debut
Cells(1, 3) = "Durée totale " & Duree
End Sub
ceci est mon deuxieme code en vba
le premier etant une recherche et un affichage de tout les nombre premier dans un interval
bien loin d'etre optimiser comme le tient mais vu qu'il ny a pas 36 solution il reprenai les meme idée(mais je tient a precisé que ces deux code n'ont eté fait sans aucune aide suf celle de mes cours de math)
a+
2 juil. 2005 à 23:13
Il faut savoir que c'est une voie très prometteuse, les personnes qui trouvent un nombre 1er de très grande taille peuvent le vendre très cher a des boites d'informatique car très recherché pour le cryptage. Encore faut-il trouver un nombre premier et prouvé sa "premiertitude"
16 mai 2005 à 22:59
J'ai étudié le gain le temps, qui se fait en évitant la boucle 'Select' (gain de 8%) et sur la suppression de la variable 'tt' (gain de 14%)... Voilà ce que cela donne :
Function nbp3(A As Long) As Boolean
'Renvoi VRAI ou FAUX selon que le nombre est premier ou pas
'Traitement A en entier positif
A = Abs(A)
If A > 211 Then GoTo suite 'évite select si pas nécessaire
'Traitement cas trivial
Select Case A
Case 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
nbp3 = True
End Select
Exit Function
suite:
'Test si multiple de 2, 3, 5, 7
If A Mod 2 = 0 Then Exit Function
If A Mod 3 = 0 Then Exit Function
If A Mod 5 = 0 Then Exit Function
If A Mod 7 = 0 Then Exit Function
'Test jusqu'à A^0.5
Dim bs As Long
Dim t As Long
bs = A ^ 0.5
For t = 0 To bs Step 210
If A Mod (t + 11) = 0 Then Exit Function
If A Mod (t + 13) = 0 Then Exit Function
If A Mod (t + 17) = 0 Then Exit Function
If A Mod (t + 19) = 0 Then Exit Function
If A Mod (t + 23) = 0 Then Exit Function
If A Mod (t + 29) = 0 Then Exit Function
If A Mod (t + 31) = 0 Then Exit Function
If A Mod (t + 37) = 0 Then Exit Function
If A Mod (t + 41) = 0 Then Exit Function
If A Mod (t + 43) = 0 Then Exit Function
If A Mod (t + 47) = 0 Then Exit Function
If A Mod (t + 53) = 0 Then Exit Function
If A Mod (t + 59) = 0 Then Exit Function
If A Mod (t + 61) = 0 Then Exit Function
If A Mod (t + 67) = 0 Then Exit Function
If A Mod (t + 71) = 0 Then Exit Function
If A Mod (t + 73) = 0 Then Exit Function
If A Mod (t + 79) = 0 Then Exit Function
If A Mod (t + 83) = 0 Then Exit Function
If A Mod (t + 89) = 0 Then Exit Function
If A Mod (t + 97) = 0 Then Exit Function
If A Mod (t + 101) = 0 Then Exit Function
If A Mod (t + 103) = 0 Then Exit Function
If A Mod (t + 107) = 0 Then Exit Function
If A Mod (t + 109) = 0 Then Exit Function
If A Mod (t + 113) = 0 Then Exit Function
If A Mod (t + 121) = 0 Then Exit Function
If A Mod (t + 127) = 0 Then Exit Function
If A Mod (t + 131) = 0 Then Exit Function
If A Mod (t + 137) = 0 Then Exit Function
If A Mod (t + 139) = 0 Then Exit Function
If A Mod (t + 143) = 0 Then Exit Function
If A Mod (t + 149) = 0 Then Exit Function
If A Mod (t + 151) = 0 Then Exit Function
If A Mod (t + 157) = 0 Then Exit Function
If A Mod (t + 163) = 0 Then Exit Function
If A Mod (t + 167) = 0 Then Exit Function
If A Mod (t + 169) = 0 Then Exit Function
If A Mod (t + 173) = 0 Then Exit Function
If A Mod (t + 179) = 0 Then Exit Function
If A Mod (t + 181) = 0 Then Exit Function
If A Mod (t + 187) = 0 Then Exit Function
If A Mod (t + 191) = 0 Then Exit Function
If A Mod (t + 193) = 0 Then Exit Function
If A Mod (t + 197) = 0 Then Exit Function
If A Mod (t + 199) = 0 Then Exit Function
If A Mod (t + 209) = 0 Then Exit Function
If A Mod (t + 211) = 0 Then Exit Function
Next t
nbp3 = True
End Function
Par contre, pour pouvoir continuer cet algorithme avec plus de suppression de multiples (par exemple jusqu'à 11), je pense faire générer au préalable, par le programme, la liste des multiples, en les mettant en mémoire. Ceci afin de substituer toutes ces lignes de tests, par la liste mis en mémoire. Faire un algo dans l'algo, en qlq sorte...
Néanmoins, lorsqu'on regarde à quel genre de chose on arrive, on remarque qu'il y a forcément un optimum qlq part. En effet, comme je l'avais dit, si on veut supprimer tous les multiples jusqu'à 11, soit la borne 2310, on a 343 nombres premiers à trouver. C'est encore raisonnable à faire générer par le PC. Mais ce nombre grimpe trés trés vite, (plus vite qu'une factorielle).
Pour 13, on a une borne=30030 soit 3248 nb premiers.
Pour 17, on a une borne=510510 soit 42331 nb premiers.
Pour 19, on a une borne=9699690 soit 646029 nb premiers...
ET là on comprends, que générer tous les premiers nombres premiers, pour les réutiliser ensuite, risque de prendre plus de temps, que de tester tout de suite avec une liste plus courte...
Enfin, je verrai cela un peu plus tard... c'était histoire de faire avancer le schimililibi.libimili.blique...
A+
Us.
10 mai 2005 à 23:10
IL reste qu'il me semble possible d'améliorer cette structure algorithmique... (et peut-être éviter tous ces tests dans "select" qui finissent surement pas être le plus pénalisant....)
Dés que j'aurais plus de temps, je me pencherais là-dessus. Car toute amélioration pour les "sauts", peut aussi servir au crible d'Eratosthène, (que je n'ai pas encore repris).
A suivre...
Us.
8 mai 2005 à 23:02
Donc au final, en eliminant un maximum de nombres premiers, tu les testes tous dans ton select case ^^
Pour le fichier, c'est un fichier à ne lire qu'une et une seule fois. Tout dépend, encore une fois, de ce que tu veux faire :)
8 mai 2005 à 22:51
IL est certain que si on voulait poursuivre le principe, on aurait de plus en plus de tests à fabriquer... c'est une conséquence que je ne sais pas contourné mathématiquement... sauf si une formulation permet une simplification... reste plus qu'à trouver une meilleur programmation... j'y réflèchirais...
Pour le fun, si je regarde ce qu'il adviendrait de la programmation, en voulant supprimer les multiples de 2,3,5,7,11 ; on aurait comme constante de "cycle" au lieu de 30 ou 210 dans les autres algorithmes : 2*3*5*7*11 = 2310 !!! Soit dans "Select Case", il faudrait tester tous les nombres premiers inférieurs à 2310... il y en a 343 !!! Ensuite, dans "For t=..." il faudrait construire la suite de tous les nombres compris entre 13 et (2310+13) qui ne soit pas multiple de 2,3,5,7,11. JE l'évalue à environ 1000 lignes de tests !!!
Bon... c'est sur que là !...courageux mais pas fou ! Je vais rester à mon nbp2... (déjà pas si mal...)
=
Histoire de...
Euh... Génèrer tous les nombres premiers inférieurs à 10 millions, met pour moi 2,50 minutes... (et avec cet algo). Avec un PC récent le temps doit être au moins réduit par 10 (voir plus) soit qlq chose ente 10 et 20 secondes (à la louche)... maintenant lire un fichier contenant tous les nombres premiers jusqu'à 10 millions est-ce rentable ?
(A savoir il y en 664579 dont la taille moyenne serait d'environ (peut-être) 7 chiffres, soit 7*664579 et plus un caractère séparateur, soit + 664579, donc 5316632 octets... qu'on divise par 1024 pour la taille en Ko et encore par 1024 pour des Mo, soit 5Mo... ce qui commence à faire... surtout si à chaque fois qu'on test la fonction, elle lit le fichier...)
A noter, en plus avec mon algo : NOMBRE DE NOMBRES PREMIERS (ALGO RAPIDE) qui utilise le crible, ce temps vaut 10 secondes pour mon Pentium II, soit surement à peine 1 seconde avec un PC récent...
=
A+
Us.
8 mai 2005 à 02:40
Tel que je te vois parti ton 'Select Case' finira par te faire tester toute la liste des nombres premiers jusqu'a 10 millions.
Ce qui revient en fait à charger un fichier les contenant...
7 mai 2005 à 20:35
J'ai trouvé une généralisation des "sauts" ! Ce qui permet de fabriquer un algorithme similaire à celui proposé, de plus en plus rapide... (enfin, sous certaines conditions...)
Mais déjà voici le nouveau algorithme de 24% à 33% plus rapide que celui proposé...
==
Function nbp2(A As Long) As Boolean
'Renvoi VRAI ou FAUX selon que le nombre est premier ou pas
'Traitement A en entier positif
A = Abs(A)
'Traitement cas trivial
Select Case A
Case 1
Exit Function
Case 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31
nbp2 = True
Exit Function
End Select
'Test si multiple de 2, 3, 5
If A Mod 2 = 0 Then Exit Function
If A Mod 3 = 0 Then Exit Function
If A Mod 5 = 0 Then Exit Function
'Test jusqu'à A^0.5
Dim bs As Long
Dim t As Long
Dim tt As Long
bs = A ^ 0.5 / 30
For t = 0 To bs
tt = 30 * t
If A Mod (tt + 7) = 0 Then Exit Function
If A Mod (tt + 11) = 0 Then Exit Function
If A Mod (tt + 13) = 0 Then Exit Function
If A Mod (tt + 17) = 0 Then Exit Function
If A Mod (tt + 19) = 0 Then Exit Function
If A Mod (tt + 23) = 0 Then Exit Function
If A Mod (tt + 29) = 0 Then Exit Function
If A Mod (tt + 31) = 0 Then Exit Function
Next t
nbp2 = True
End Function
==
UN mot d'explication... (en essayant de faire plus direct)
TOUTE l'idée consiste à tester le nombre A, par divisions successives avec tous les nombres inférieurs à sa racine carré... Et pour aller plus vite, on réduit la liste des nombres testeurs en supprimant déjà quelques multiples de nombres premiers.
EN particulier, en supprimant les multiples de 2, en retrouve l'idée très connues, de prendre que les nombres impairs... Bien sur, en assurant que le nombre A à tester n'est pas pair...
EN continuant, en supprimant les multiples de 2 et 3. On retrouve l'idée utilisée dans mon algorithme (en haut de page)... La liste des nombres testeurs est alors générée avec la forme 6p+/-1.
ET rien empêche de poursuivre cette idée. En supprimant les multiples 2, 3 et 5. On obtient alors, ce dernier algorithme proposé dans ce post (juste au-dessus).
ON peut poursuivre ainsi, aussi loin que l'on veut... J'ai d'ailleurs essayé un algorithme en supprimant 2,3,5,7. Ce qui donne ce qui suit :
=
Function nbp3(A As Long)
'Renvoi VRAI ou FAUX selon que le nombre est premier ou pas
'Traitement A en entier positif
A = Abs(A)
'Traitement cas trivial
Select Case A
Case 1
Exit Function
Case 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
nbp3 = True
Exit Function
End Select
'Test si multiple de 2, 3, 5, 7
If A Mod 2 = 0 Then Exit Function
If A Mod 3 = 0 Then Exit Function
If A Mod 5 = 0 Then Exit Function
If A Mod 7 = 0 Then Exit Function
'Test jusqu'à A^0.5
Dim bs As Long
Dim t As Long
Dim tt As Long
bs = A ^ 0.5 / 210
For t = 0 To bs
tt = 210 * t
If A Mod (tt + 11) = 0 Then Exit Function
If A Mod (tt + 13) = 0 Then Exit Function
If A Mod (tt + 17) = 0 Then Exit Function
If A Mod (tt + 19) = 0 Then Exit Function
If A Mod (tt + 23) = 0 Then Exit Function
If A Mod (tt + 29) = 0 Then Exit Function
If A Mod (tt + 31) = 0 Then Exit Function
If A Mod (tt + 37) = 0 Then Exit Function
If A Mod (tt + 41) = 0 Then Exit Function
If A Mod (tt + 43) = 0 Then Exit Function
If A Mod (tt + 47) = 0 Then Exit Function
If A Mod (tt + 53) = 0 Then Exit Function
If A Mod (tt + 59) = 0 Then Exit Function
If A Mod (tt + 61) = 0 Then Exit Function
If A Mod (tt + 67) = 0 Then Exit Function
If A Mod (tt + 71) = 0 Then Exit Function
If A Mod (tt + 73) = 0 Then Exit Function
If A Mod (tt + 79) = 0 Then Exit Function
If A Mod (tt + 83) = 0 Then Exit Function
If A Mod (tt + 89) = 0 Then Exit Function
If A Mod (tt + 97) = 0 Then Exit Function
If A Mod (tt + 101) = 0 Then Exit Function
If A Mod (tt + 103) = 0 Then Exit Function
If A Mod (tt + 107) = 0 Then Exit Function
If A Mod (tt + 109) = 0 Then Exit Function
If A Mod (tt + 113) = 0 Then Exit Function
If A Mod (tt + 121) = 0 Then Exit Function
If A Mod (tt + 127) = 0 Then Exit Function
If A Mod (tt + 131) = 0 Then Exit Function
If A Mod (tt + 137) = 0 Then Exit Function
If A Mod (tt + 139) = 0 Then Exit Function
If A Mod (tt + 143) = 0 Then Exit Function
If A Mod (tt + 149) = 0 Then Exit Function
If A Mod (tt + 151) = 0 Then Exit Function
If A Mod (tt + 157) = 0 Then Exit Function
If A Mod (tt + 163) = 0 Then Exit Function
If A Mod (tt + 167) = 0 Then Exit Function
If A Mod (tt + 169) = 0 Then Exit Function
If A Mod (tt + 173) = 0 Then Exit Function
If A Mod (tt + 179) = 0 Then Exit Function
If A Mod (tt + 181) = 0 Then Exit Function
If A Mod (tt + 187) = 0 Then Exit Function
If A Mod (tt + 191) = 0 Then Exit Function
If A Mod (tt + 193) = 0 Then Exit Function
If A Mod (tt + 197) = 0 Then Exit Function
If A Mod (tt + 199) = 0 Then Exit Function
If A Mod (tt + 209) = 0 Then Exit Function
If A Mod (tt + 211) = 0 Then Exit Function
Next t
nbp3 = True
End Function
=
Les performances de ce dernier, semble s'améliorer plus la taille des nombres à tester est grande par rapport aux deux autres algorithmes (haut de page et le premier dans ce post)
Pour les tester, j'ai mesuré le temps mis pour tous les nombres de 1 à 10 millions?
Sur mon Pentium II, j'ai obtenu pour le premier algorithme, en haut de page : 255 secondes.
Pour le premier algorithme de ce post : 167 secondes.
Pour le dernier algorithme de ce post : 165 secondes?. Pour ce dernier, avec une borne inférieure, il est moins performant que le précédent. La borne 10 millions, semble être la limite ou ce dernier commence à dépasser le précédent? A noter, que pour les 3 algorithmes, les écarts ne sont pas constant et dépendent de la borne?
Bon?. enfin, je suis assez satisfait maintenant? mais il reste des améliorations à apporter? la plus grande serait de trouver une véritable formule pour retranscrire les « tt + Cte » qui simplifierait la généralisation de l'algorithme à n'importe quelle liste de nombre testeur sans multiple d'un certain nombre de nombre premier.
Amicalement,
Us.
7 mai 2005 à 00:42
C'est par exemple, trouver la suite sans multiple de 2 et 3 = On sait déjà le faire c'est l'algo au-dessus...
Ensuite, c'est de nouveau trouver la suite sans multiple de 2 et 3 et 5... etc...
Us.
7 mai 2005 à 00:36
Us.
7 mai 2005 à 00:35
Eh bien, si tu trouves, un très grand bravo parce que ca n'existe toujours pas. Pour la bonne raison qu'a part le crible d'Eratostene, on n'a rien trouvé...
Maintenant de quoi parles-tu au point de vue rapidité ? Tu veux savoir si un nombre est premier d'une manière très rapide ou alors simplement avec un algo rapide ?
Dans le premier cas, passe à l'assembleur en gardant ton algo et tu auras les meilleurs résultats.
Dans le second cas, ton algo est déjà très bien :)
6 mai 2005 à 20:27
Comme quoi, y'a peut-être des moyens de généraliser les formules... (mieux que ce j'ai vu...)
Us.
6 mai 2005 à 20:08
Pour l'algorithme en lui-même... je suis partiellement d'accord avec toi... pour trouver un nombre premier P, il faut le tester par division... Et à ce propos, hier soir j'ai testé tous les algorithmes trouvés sur VBFrance pour trouver le plus rapide... ce qui m'a permis de reformuler mon algorithme, qui est objectivement le plus rapide du site maintenant...
J'AI dis partiellement d'accord... En effet, le crible d'Eratosthène (voir mon algo) ne fait pas intervenir de division, ni de calcul dans son principe... C'est donc bien une méthode différente...
=
(Après coup, je m'aperçois que je suis trés bavard, en espérant que la suite, ne vous soit pas pénible... sinon je comprendrais...)
=
A ce sujet, j'en profite pour vous exposer une idée que je n'ai pas eu encore le temps de programmer et de tester... En fait, elle rejoint autant l'utilisation du crible d'Eratosthène que celle utilisée dans l'algo ci-dessus consistant à utiliser les nombres impairs par saut de 6p+/-1... Car dans les deux cas, les "sauts" ont permis un gain important de la rapidité... Elle m'est apparut naturelle en étudiant le crible, que j'ai déposé... Elle consiste, tout simplement à trouver une généralisation des "sauts" dans la liste des nombres impairs...
EN clair et dans le détail : comme dans le crible d'Eratosthène, on démarre par la liste des nombres : 1, 2, 3, 4, etc... Au délà de 2, on peut supprimer les nb pairs (classique)... IL reste : 3, 5 ,7, 9 , 11, 13, etc... (tj trés classique)... c'est en particulier, (hors 3) l'utisation de 6p+/-1... Si maintenant on continue pour supprimer les multiples de 3, et qu'on recherche une formule pour exprimer la liste restante (c'est donc une suite logique, pour généraliser les "sauts", qui résulte du principe du crible)... IL reste : 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, etc... Pour calculer cette suite dans une boucle, il faut regarder comment reconstruire cette suite, soit :
X Y
-----------------
0 5
1 7
2 11
3 13
4 17
5 19
6 23
7 25
8 29
9 31
10 35
11 37
12 41
13 43
14 47
15 49, etc...
J'ai trouvé la relation : Y 3*X+4,5+((-1)^x)/2. Et comme il est aussi intéressant selon les bessoins de faire l'inverse : X (Y-4,5 - (-1)^MOD(Y;3)/2)/3... Plus dur à utiliser...
On peut également regarder la suite (c'est pour ça que je parle de généralisation)... Sans les multiples de 5...
0 7
1 11
2 13
3 17
4 19
5 23
6 29
7 31
8 37
9 41
10 43
11 47
12 49
13 53
14 59
15 61
16 67
17 71
18 73
19 77
20 79, etc...
Là , la relation devient vraiment plus évidente... Et c'est là où trouver une généralisation "pratique" serait trés fort... A savoir : Y = 3,75*X+6+Cte ... "Cte" prends alternativement en boucle les valeurs suivantes : {4, 5, -2, -1, -8,-7, 2, -5}... On trouve deux trois p'tits choses en plus, mais rien de super facile...
Si on regarde ensuite sans les multiples de 7, on a toujours sur le même principe une relation linéaire avec une Cte, avec un cycle vraiment trés important cette fois... (je ne suis arrêté là)...
IL n'empêche que si on arrive à généraliser ces "sauts" (ou même seulement à bien les programmer), il y a des chances qu'on obtienne un algorithme encore plus rapide... IL suffit, pour s'en convaincre de regarder la réduction auquel on arrive... Par exemple, Pour 2, on réduit le nombre de division par 50% (à peu de chose prés). Pour 3, encore de 16,66%. Pour 5, encore 10%... Pour 7, plus que 3,33...%... soit au total 80%... sauf erreur...
Bien sur, pour que l'algorithme soit optimal, il ne faut pas que le calcul du saut devienne plus long que les divisions qu'elle évite...
Bref, j'vais essayer tout ça... mais il reste encore vraiment encore beaucoup de pain sur la planche... et un peu d'aide, cela ne sera pas de refus...
Voilà !
Amicalement,
Us.
6 mai 2005 à 08:30
Les nombres premiers sont connus depuis les grecs, donc les algos pour vérifier la primalité, ben ca m'étonne pas qu'on en invente pas tous les jours en fait ^^
Et puis la seule chose à faire pour le moment, c'est vérifier que de plus petits chiffres ne le divisent pas, après c'est simplement une question de méthode.
6 mai 2005 à 01:30
3 mai 2005 à 11:02
IL me semble être le seul (sans me vanter) dans mon post sur le calcul de Pi(x) (nombre de nombre premier) à avoir mis en oeuvre une amélioration pour le crible d'ératosthème, par rapport à tout ce qu'on trouver. Les autres algorithmes ne font que reprendre des idées déjà bien rodée... et j'espère assez bien programmer, grâce à votre aide...
Bon... bon... je chercherai encore...
Beaucoup de manières de voir si un nombre n'est pas premier ? ... Il faudrait détailler un peu, et/ou indiquer un site sur le sujet qui soit exploitable...
En l'état, pour cet algorithme, je ne suis pas arrivé à trouver mieux, même en exploitant les idées du crible ou bien ceux de la décomposition en facteurs premiers (en prenant que les nb de la forme 6p-1 ou 6p+1)... Il me semble d'ailleurs que chacun des algorithmes soient optimums dans leur catégorie... (un peu curieux donc, qu'ils ne sont pas basés sur les mêmes idées)...
Us.
3 mai 2005 à 08:19
3 mai 2005 à 00:03
2 mai 2005 à 23:18
Cherche un peu sur Google et apprend les joies de ces nombres si particuliers...
2 mai 2005 à 22:00
Je viens de changer le code...
Une simple question : Connaissez-vous un meilleur algorithme ?
Sincère remerciement,
Amicalement,
Us.
2 mai 2005 à 15:06
Mais il m'a fallu 900 000 boucles pour mettre en évidence un écart significatif.
2 mai 2005 à 13:22
If (A AND 1)=0 then
NbP = False
Exit Function
end if
2 mai 2005 à 11:01
De plus j'ai omis le cas où A<=1...
A rajouter donc :
If A <1 Then NbP False: Exit Function
Amicalement,
Us.
2 mai 2005 à 09:30
Il m'a fallu 100000 itérations sur les 2 méthodes que je t'ai présentées pour voir que la seconde est environ 10 fois plus rapide que la première. Avec moins d'itérations, les deux semblent de vitesse égale.
Bien sûr, si tu lances la fonction NbP dans une boucle, la différence de performance risque de se voir.
2 mai 2005 à 09:22
Dans la première méthode, tu ne vérifies que le dernier chiffre (ce qui est tout à faire correct du point de vue mathématique). Mais tu es obligé de faire appel aux fonctions Val, Right et Str, ce qui ralentit ton processus.
Du coup, A mod B devient plus rapide que de regarder le dernier chiffre.
Rapide, mais pas top :
If Val(Right(Str(A), 1)) Mod 2 = 0 Then Nbp= False
Beaucoup plus rapide :
If A Mod 2 = 0 Then Nbp= False
2 mai 2005 à 08:59
If A Mod t = 0 Then
NbP = False
Exit Function
Else
NbP = True
End If
Next t
Le ELSE ne sert à rien, et génère du temps perdu.
En effet, l'intérêt de la boucle, c'est de mettre ou pas le flag NbP à False. On s'en fiche de le remettre à True à chaque fois que 'A' n'est pas divisible par 't'.
NbP = True
For t = 3 To Int(A ^ 0.5) Step 2
If A Mod t = 0 Then
NbP = False
Exit Function
End If
Next t
Comme çà, tu ne rentreras pas (un nombre incalculable de fois) dans le ELSE, pour rien.