NOMBRES PREMIERS - ERATOSTHENE QUASI ILLIMITÉ
nightlord666
Messages postés
746
Date d'inscription
vendredi 17 juin 2005
Statut
Membre
Dernière intervention
23 mai 2007
-
13 oct. 2006 à 18:47
_michel Messages postés 77 Date d'inscription mardi 27 juin 2006 Statut Membre Dernière intervention 12 août 2010 - 6 nov. 2006 à 09:08
_michel Messages postés 77 Date d'inscription mardi 27 juin 2006 Statut Membre Dernière intervention 12 août 2010 - 6 nov. 2006 à 09: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/39906-nombres-premiers-eratosthene-quasi-illimite
https://codes-sources.commentcamarche.net/source/39906-nombres-premiers-eratosthene-quasi-illimite
6 nov. 2006 à 09:08
Enfin je préfère le bon vieux crible, il me semble quand même plus performant (la preuve : l'algorythme le plus (ou peut être un des plus) puissant est basé sur le crible lui-même (crible d'Atkin)).
3 nov. 2006 à 16:42
Il faudrait aussi vérifier que Maxpile > 4 (à toi de voir ...)
1 nov. 2006 à 12:06
Je vais essayer de chercher la faille, si je trouve le temps et la motivation (quel plaisir, la chasse aux bugs...).
En tout cas, j'espère que ce n'est pas mon PC, je l'ai depuis à peine trois mois !
En attendant de trouver le problème, bonne programmation.
31 oct. 2006 à 12:01
On pourrait avoir un plantage en ligne 62! :((
Je n'ai jamais rencontré ce problème, mais quand n=MAXPILE-1 , on y calcule P[2*MAXPILE+1] et ça fait un peu trop dans la mesure où on alloué 2*MAXPILE ...
Quand même curieux que je n'aie jamais rencontré ce cas !!
30 oct. 2006 à 13:45
J'ai essayé plusieurs fois (avec 100 ou sans argument c'est la même chose), et les résultats sont variables!!!
Un coup il le fait instantanément, je réessaye et la il plante.
Curieux, non?
En tout cas moi j'ai jamais vu ça.
D'autant plus que de la part d'un programme de 80 lignes, c'est étonnant.
Enfin bref, j'ai vérifié l'allocation : nickel.
Je vais voir ça plus précisement, parce que ça m'intrigue.
Pour l'instant, je pense qu'il y a un P[x] non alloué quelque part, et des fois ça pose pas de souci, des fois si.
PS : J'ai essayé avec deux compilateurs (bcc55 et dev-cpp), a priori mêmes résultats.
30 oct. 2006 à 12:27
J'ai repris le source fourni tel quel et je l'ai recompilé : no problem !
Essaie de supprimer les optimisations dans les options de compilation (/Od pour µSoft Visual C++).
En général les optimisations créent plus de problèmes que ça n'en résout !
En ligne 40 tu peux aussi ajouter :
if (!P)
{
printf("Impossible d'allouer %d octets.\n", 2*MAXPILE*sizeof(unsigned long));
return;
}
pour le cas où l'allocation aurait raté !
Sinon, tu n'as plus qu'à mettre des "printf", pour voir où tu bloques ...
Tu peux aussi mettre la fonction suivante (modifiée par rapport au source fourni)
void dumpPile(int n)
{
int i;
n = 2*n ;
for (i=n+1; i>=0; i-=2)
printf("%d:%d ", gP[i], gP[i-1]); /* +grd multiple trouvé : premier */
printf("\n");
}
et insérer un "dumpPile(n);" avant la ligne 52.
Pour Erat 10, tu dois obtenir :
Liste des 10 premiers nombres premiers
2 - 3 - 5 - 7 14:7 10:5 9:3
14:7 12:3 10:5
- 11 22:11 15:5 14:7 12:3
- 13 26:13 22:11 15:5 15:3 14:7
26:13 22:11 21:7 15:5 15:3
26:13 22:11 21:7 18:3 15:5
- 17 34:17 26:13 22:11 21:7 20:5 18:3
- 19 38:19 34:17 26:13 22:11 21:7 21:3 20:5
38:19 34:17 26:13 25:5 22:11 21:7 21:3
38:19 34:17 26:13 25:5 24:3 22:11 21:7
38:19 34:17 28:7 26:13 25:5 24:3 22:11
- 23 46:23 38:19 34:17 33:11 28:7 26:13 25:5 24:3
46:23 38:19 34:17 33:11 28:7 27:3 26:13 25:5
46:23 38:19 34:17 33:11 30:5 28:7 27:3 26:13
46:23 39:13 38:19 34:17 33:11 30:5 28:7 27:3
46:23 39:13 38:19 34:17 33:11 30:5 30:3 28:7
- 29
28 oct. 2006 à 18:19
lol
Non, sans blague, j'ai executé ton programme sans argument, et même comme ça il fonctionne pas.
C'est peut-être à cause du compilateur.
28 oct. 2006 à 15:42
_MICHEL : ce n'est pas normal : Sur mon PIV, 2.4Ghz, un "prem 1000" dure moins d'une seconde. Faute de frappe ?
27 oct. 2006 à 23:18
27 oct. 2006 à 22:19
Ensuite, je l'ai fermé.
Est-ce normal?
Sinon, si ca t'interesse, moi aussi j'ai fait un générateur de nombre peremier (pas trop mal, j'en suis fier, mais on m'a donné des conseils pour l'optimisation).
24 oct. 2006 à 17:57
Pour POLE4 : ce code ne renvoie pas tous les premiers<n mais les n premiers.
Je sais que l'explication qui suit n'est pas simple, mais je ne sais pas comment vous le dire autrement !
Exemple de dump pour expliquer le fonctionnement
Premiers : 2 - 3 - 5 - 7
14-7 10-5 9-3 Pile initiale
14-7 12-3 10-5 Multiple de 3 suivant, bien placé (9+3 -> 12-3)
15-5 14-7 12-3 Multiple de 5 suivant, bien placé (10+5 -> 15-5)
Premier : 11 10+1 < 12 donc 11 premier
(comparaison "10-5" et "12-3")
22-11 15-5 15-3 14-7 11 mis dans la liste, avec son premier multiple (22)
Premier : 13 12+1 < 14 donc 13 est premier ("12-3" et "14-7")
26-13 22-11 21-7 15-5 15-3 13 est mis dans la liste et le multiple de 7 est placé
26-13 22-11 21-7 18-3 15-5 Multiple de 3 suivant, bien placé (15+3 -> 18-3)
26-13 22-11 21-7 20-5 18-3 Multiple de 5 suivant, bien placé (15+5 -> 20-5)
Premier : 17 15+1 < 18 donc 17 est premier (impair suivant 15+1=16)
34-17 26-13 22-11 21-7 21-3 20-5 17 est mis dans la liste
Premier : 19 18+1 < 20 donc 19 est premier
38-19 34-17 26-13 25-5 22-11 21-7 21-3 Multiple de 5 suivant, bien placé (20+5 -> 25-5)
38-19 34-17 26-13 25-5 24-3 22-11 21-7 ...
Une fois qu'on a supprimé tous les pairs, on prend la première valeur non barrée : 3 et on regarde ses multiples.
2*3 = 6 ! On a sauté au-dessus de 5 (impair), donc 5 est premier. On regarde les multiples de 5. 2*5=10.
Entre 5 et 9 (prochain multiple de 3), on a 7, qui est donc premier.
On reprend 3, puisqu'on est arrivé à 9, pour calculer 9+3=12. Entre 10 (dernier multiple de 5 trouvé) et 12, on a un impair : 11. Donc il est premier. etc.
En ligne 52, 'c' contient le premier en cours de traitement, 'b' son dernier multiple calculé et 'a' le multiple suivant.
En ligne 56, on regarde si ce nouveau multiple est plus grand que le dernier multiple calculé du nombre premier suivant dans la liste ! (facile !)
Si oui, on insère la paire (multiple premier) = (a c) à sa place dans la liste (décalage paire par paire, qui aurait pu être un décalage de bloc, mais pas dans un contexte de machine à pile).
En ligne 70, on trouve le nombre impair suivant 'b' : ex : si 'b'=10, alors (('b'+1) | 1) = (11 | 1) = 11; si 'b'=19, alors (('b'+1) | 1) = (20 | 1) = 21.
En ligne 72, 'b' est le dernier multiple calculé du nombre premier qu'on traitera ensuite, et 'c' est le multiple du dernier de la liste (a priori la plus grande valeur trouvée jusque là).
La boucle en ligne 75, énumère les nombres impairs entre le nombre impair suivant calculé précédemment et 'b', les ajoute à la liste (avec leur premier multiple : 2x) et affiche les nombres trouvés.
A priori la boucle doit ête inutile car il me semble qu'on ne peut trouver qu'un nombre à la fois, mais dans le doute ...
Voilà, vous savez tout !
ps. mon avatar, s'il veut bien s'afficher) est la version Piet de ce programme (cf http://www.dangermouse.net/esoteric/piet.html)
17 oct. 2006 à 17:02
On peut facilement trouver un nombre premier de 1000 chiffres, mais on est loin de savoir combien il y a de nb premiers jusqu'à 10^1000(record : 4*10^22) et encore plus de les connaître tous (record : 10^16).
16 oct. 2006 à 22:07
16 oct. 2006 à 11:28
D'accord avec toi pour les include, mais comme le compilateur ne fait pas la différence, je mets une fois l'un, une fois l'autre !
En ce qui concerne la variable en majuscules, au départ c'était une constante, mais j'ai décidé d'en faire un paramètre (grosse flemme, quoi !).
Pas de test des codes retours : en fait au départ j'ai écrit ce programme pour le faire marcher en BrainFuck et en Piet (en gros, sur une machine de Turing), donc mettre en place des tests ce n'était pas vraiment facile, et ensuite je voulais le soumttre à un OCC, donc plus c'est court et abscons et mieux c'est. OK, pour ce post, j'aurais dû faire mieux ! D'ailleurs, tu n'as pas remarqué que je ne libère pas non plus la mémoire allouée ;)
Paramètre en dessous de 6 : ça fonctionne ! Mais en dessous de 4, on affiche toujours 4 valeurs au minimum. Par contre ça plante pour 1 (rappel : aucun test !).
pour Kirua.
Je ne "barre" aucune valeur, c'est ce qui fait la spécificité de cet algo.
Dès que j'ai un peu de temps, je mets un petit texte explicatif.
Merci pour vos commentaires.
15 oct. 2006 à 21:04
Un nombre est premier avec un autre si leur PGCD est 1.
pi(n) renvoie bien le nb de nb premier inférieur à n.
15 oct. 2006 à 18:25
http://villemin.gerard.free.fr/Wwwgvmm/Premier/quantiPi.htm
je ne crois pas me tromper.
15 oct. 2006 à 15:42
Ce n'est pas pi(n) mais phi(n) et elle renvoit les nombres premiers à n et inférieur à n et pas les nombres premiers !
14 oct. 2006 à 12:52
Si tu veux obtenir ts les nombres premiers codables sur 32 bits, le plus facile (pas forcément le plus rapide, hmm ^^) est d'utiliser eratosthène jusque la racine carrée de 2^32, soit 2^16 65 536: ça ça prend même pas une milliseconde. Ensuite, pour ts les nombres de 2^36 + 1 à 2^32 - 1 tu testes la divisibilité (% 0) par les nombres premiers ainsi trouvés. Tu passes évidemment les multiples de 2, ça va sans dire, mais il y a moyen de passer encore plus de nombres que ça.
Ça tournera pendant quelques secondes, voire une pleine minute, mais ça marchera je pense (1/3 des nombres impairs étant divisible par 3 (et en continuant le calcul), c'est facile de montrer que dans la plupart des cas, tu ne feras pas plus de 4-5 opérations % sur les nombres testés. Pour les nombres effectivement premiers, tu feras par contre pi(2^16 - 1) opérations, ce qui vaut 6542. Nb: la fonction "pi(n)" renvoie le nombre de nombres premiers inférieurs à n.
Avec cette méthode, la mémoire ne sera pas un problème puisque tu auras simplement à enregistrer (par exemple tout de suite sur le disque) les nombres effectivement premiers.
Bonne continuation, c'est cool les algos pr les nombres premiers ^^.
PS: il y a moyen d'énormément optimiser le crible d'eratosthène; passe un peu de temps à observer quels tests sont inutiles. Par exemple, quand tu "barres" les nombres, comme tu as sûrement déjà barré les nombres pairs à l'avance, c'est pas la peine de les rebarrer.
13 oct. 2006 à 18:47
- Normalement, les includes standards s'écrivent sous la forme <stdio.h>, et pas "stdio.h" : les "" cherchent dans le répertoire courant de l'application.
- On met uniquement les noms des constantes en majuscule, même si ce n'est pas une obligation, c'est une norme que tout le monde devrait respecter, car ça aide beaucoup dans la lecture d'un programme inconnu.
Ensuite, tu ne vérifie pas les valeurs de retour des fonctions : tu alloue de la mémoire sans vérifier si elle est bien allouée (très risqué dans un programme comme ça), et si elle n'est pas bien allouée, tu t'en fiches, ça provoquera juste une erreur de segmentation...
Encore une autre erreur que j'ai trouvé : quand tu met un nombre en dessous de 6 dans le nombre de nombres premiers à afficher, tu accèdera à la case mémoire P[5], qui sera invalide, et qui provoquera une erreur de segmentation.
Sinon, commente ton programme, car je ne vois pas du tout comment il fonctionne (remarque que j'ai pas non plus beaucoup cherché aussi ;)).
Sinon, le programme marche bien, et il m'a l'air assez rapide.