.: NOMBRES PREMIERS ET PARFAITS :: DECOMPOSITION FACTEURS PREMIERS :.
vjeux
Messages postés
92
Date d'inscription
lundi 14 avril 2003
Statut
Membre
Dernière intervention
5 décembre 2003
-
21 mai 2003 à 16:18
Saros Messages postés 921 Date d'inscription vendredi 20 décembre 2002 Statut Membre Dernière intervention 23 septembre 2010 - 28 avril 2005 à 08:42
Saros Messages postés 921 Date d'inscription vendredi 20 décembre 2002 Statut Membre Dernière intervention 23 septembre 2010 - 28 avril 2005 à 08:42
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/7173-nombres-premiers-et-parfaits-decomposition-facteurs-premiers
https://codes-sources.commentcamarche.net/source/7173-nombres-premiers-et-parfaits-decomposition-facteurs-premiers
28 avril 2005 à 08:42
Et ils ont réussi à démontrer que l'ensemble des valeurs positives prises est exactement l'ensemble des nombres premiers ? Ca a pas dû être une mince affaire
27 avril 2005 à 22:47
Perso, j'ai des livres qui parle du sujet... (nb premiers)...
Cette formule est assez connue, mais totalement inutilisable ! ... et petite erreur, elle a 26 variables (et non 23, bête que je suis !)
J'ai trouvé sur internet une page sur le sujet qui reprends assez bien tous ce qu'on peut lire sur cette formule ...
http://www.lifl.fr/~wegrzyno/FormulPrem/FormulesPremiers6.html
Voilà.... donc.... bon plaisir....
Amicalement,
Us.
26 avril 2005 à 12:52
:)
26 avril 2005 à 03:02
24 avril 2005 à 19:42
==
"Il existe aussi une formule mathématique qui donne tous les nombres premiers les uns derrières les autres. f(x) = Xeme nombre premier. Mais elle est très complexe."
POUR info, cette formule possède 23 variables (pour sa version simplifiée) et n'a aucun intérêt pour le calcul. (temps extrêment long, d'ailleurs elle a été testée que pour la valeur 2 !!!). Cette formule n'a qu'un intérêt théorique ! et encore...
Adieu formule magique !
Us.
24 avril 2005 à 19:28
POUR l'algo au-dessus, il corresponds au crible d'ératothène... ET j'ai longtemps recherché (par moi-même) plus rapide, sans trouver...
IL tient au fait qu'on utilise à "plein régime" la mémoire sans jamais faire un seul calcul... juste un adressage dans un tableau... Pour les PC actuels, l'algo d'ératothène est suffissament efficace pour une borne d'environ 10000000.... mais il est préférable de tester progressivement cette borne...
BON, bon, tout ça pour dire, que j'ai également fait un algo similaire mais légèrment optimisé... dans le sens où on se contente de marquer que les nombres dans la liste des nombres impairs. ET de marquer les nombres qu'à partir du nombre carré... (les autres étant forcément déjà fait...) C'est un peu chariabia... mais trés simple dans les faits.... Alors voici ce que cela donne en vba dans une Sub appelé dans un bouton, et avec la valeur de n (dernier nombre) placé dans la cellule "B2" :
==============
Private Sub CommandButton1_Click()
fin = Range("B2").Value
ReDim nb((fin - 3) / 2) As Byte '1 octet par nombre
temps = Timer
For liste = 0 To ((fin ^ 0.5) - 3) / 2 Step 1
If nb(liste) = 0 Then
jump = (2 * liste) + 3
Else
GoTo boucle:
End If
For t = ((jump ^ 2) - 3) / 2 To (fin - 3) / 2 Step jump
nb(t) = 1
Next t
boucle:
Next liste
MsgBox "Durée :" & (Timer - temps)
For t = 0 To (fin - 3) / 2 Step 1
If nb(t) = 0 Then
b = b + 1
End If
Next t
MsgBox b + 1 ' (+1 tient compte du seul nb pair premier 2)
End Sub
===============
C'est un programme brut, il n'affiche pas les nombres premiers qui sont en mémoire, (à vous de l'adapter à vos bessoins)... IL compte ensuite le nombre de nombre premier....
Pour connaitre quel nb est premier, il suffit d'interoger le tableau. S'il vaut 1 alors pas premier, si il vaut 0, alors premier...
Par exemple avec un truc du genre :
If NB((A - 3) / 2) = 1 Then
msgbox "Pas premier"
Else
msgbox "Premier"
End If
avec A la valeur à tester... (et inférieur à la borne " fin ")
De plus le temps d'exécution est vraiment incroyable rapide.... (bien sur s'allonge avec la borne fin...)
Pour exemple, sur mon antique pentium II, pour générer en mémoire (donc) tous les nb premiers compris entre 0 et 1 million (1000000) ! il mets 0,55 secondes... QUI DIT MIEUX ?
Amicalement,
Us.
4 déc. 2004 à 01:46
29 juil. 2003 à 16:57
list.clear
redim T(1 to N) as boolean
for i=2 to N2
for j=i+i to N step i : t(j)=true : next j
next i
for i=2 to N
if not t(i) list.add i
next i
plus rapide : pas possible !
Par contre, il faut connaitre au depart la borne maxi.
Il existe aussi une formule mathématique qui donne tous les nombres premiers les uns derrières les autres. f(x) = Xeme nombre premier. Mais elle est très complexe. Par contre, elle ne necessite pas de connaitre la borne maxi.
8 juin 2003 à 13:03
C'est là qu'est le problème car ce n'est que sur ce bouton qu'il y a l'erreur, puisque la valeur écrite dans le listbox haut dessus de ce bouton est toujours la valeur entrée (si cette valeur est un des nombres premier)
8 juin 2003 à 10:18
8 juin 2003 à 10:16
7 juin 2003 à 18:12
J'ai dl ton prog et je l'ai immédiatement essayé :
Je trouve l'idée plus qu'intéressante, surtout le fait de calculer les n premiers nombres premiers, ou encore de les calculer de 1 à n.
Cependant, et je trouve cela dommage, j'ai constaté un bug !
En effet, il se trouve que quand n=7, il me dit que ce nombre n'est pas un nombre premier, d'où mon étonnement !!!. De surcroit, lorsque je demande au programme de calculer les nombres premiers de 1 à 20, il me sort tout naturellement 1, 2, 3, 5, 7, 11, 13, .... !!!!!!
Donc j'en déduit que 7 est un nombre premier (quoique je le savais déjà).
Il fais cela avec d'autres nombres premiers sauf 1 (peut-être d'autres, mais j'ai pas essayé tout les nombres premiers : il y en a un peu beaucoup).
J'aimerais donc savoir à quoi est dû ce bug, et surtout, s'il est commun seulement à moi !
Merci de ta compréhesion et bonne programmation
P.S. : Ton prog reste tout de même correct.
21 mai 2003 à 21:54
http://www.codeproject.com/dotnet/PrimeNumbersProjects.asp
21 mai 2003 à 21:45
Alors tu te lances dans les algos ?
Efficace ton prog même s'il existe des algos plus rapides... Et j'aime bien la sobriété de l'interface. Tu est assez éclectique dans le choix de tes projets... et VB.NET c'est pour quand ?
@+
Maurice
21 mai 2003 à 21:13
La source est plutôt dure à comprendre : tu utilises que algorithme pour vérifier si un nombre est premier ?
À part ce point le tout a l'air vachement optimisé (comme j'arrive pas bien à discerner le fonctionnement je peux pas dire...), joli boulot...
8/10
A+
Saros
21 mai 2003 à 20:45
1+2+3=6
1*2*3=6
6 est un nombre parfait.
Pour le msgbox timer - b faut que je le vire ça m'a juste servi à regarder combien de temps il m'était.
21 mai 2003 à 17:31
Optimisation, hmmm ?
Pour commencer : DoEvents dure 1 milliseconde. Si tu l'utilise pour rafraichir l'écran à chaque itération, ton programme sera donc automatiquement limité à 1000 itération par seconde là où est le doevents... ya pas vraiment de solutions pour éviter ça, a part un deuxième thread, ou de faire un doevents uniquement toute les 10000 itérations (if i mod 10000 = 0 then doevents) ...
Je vois aussi :
for i = ...
if truc > sqr(num) then
il vaux mieux calculer la racine carré avant l'itération pour éviter que le prog s'embête à recalculer à chaque fois. Cette remarque est valabe en d'autres endroits.
Ya encore des truc ailleur, parce que pour calculer 20000 nb prems, ça mets 60 secondes, et ya des algo sur vbfrance qui ne mettent que 1 secondes...
21 mai 2003 à 17:12
21 mai 2003 à 16:47
MsgBox Timer - b
Ca doit etre :
MsgBox Timer - a
Enfin ... c juste a mon avis ...
21 mai 2003 à 16:18
J'aime bien ton proggramme !
Sinon : j'ai que 13 ans et qu'est ce qu'un nombre parfait !?
Sinon mets des on error resume next car il y a pleins d'erreurs surtout quand on met rien :D