Accueil > > > NOMBRES PREMIERS - ERATOSTHENE QUASI ILLIMITÉ
 NOMBRES PREMIERS - ERATOSTHENE QUASI ILLIMITÉ
 Information sur la source
 Description
Ce petit programme (80 lignes) affiche tous les nombres premiers. Paramètre : combien vous en voulez (100 par défaut). Il est basé sur le fameux crible d'Eratosthène, mais contrairement à l'habitude on ne parcourt le tableau qu'une fois, en 'cochant' les non-premiers au fur et à mesure. Attention, pas de test d'erreur dans ce code ! Le programme est très simple, l'algo aussi (si, si!), mais vous aurez peut-être quand même du mal à suivre ... A l'origine je voulais le soumettre, après 'amélioration', à un concours ObfuscatedC, mais je n'ai pas le temps ! ps. J'ai fait le même en Piet, pour les amateurs ...
 Source
- /* **************************************************** */
- /* Erat.C */
- /* **************************************************** */
- /* Affichage des N premiers premiers */
- /* **************************************************** */
- /* (c) BZRD - 2006 */
- /* **************************************************** */
-
- #include "stdio.h"
- #include "stdlib.h"
- #include "memory.h"
-
- unsigned long *P;
-
- /*
- // Pour afficher le contenu du buffer, éventuellement (ce qui explique que P soit en globale)
- void dumpPile(char *msg, int n)
- {
- int i;
-
- printf("%s -- ", msg);
- n = 2*n + 4;
- for (i=n-1; i>=0; i--)
- printf("%d ", P[i]);
- printf("\n");
- }
- */
-
- void main(int argc, char **argv)
- {
- unsigned long n = 2;
- unsigned long a,b,c;
- unsigned long k, i;
- unsigned long MAXPILE = 100;
-
- if (argc > 1)
- MAXPILE = atoi(argv[1]);
-
- P = (unsigned long *)malloc(2*MAXPILE*sizeof(unsigned long));
-
- // Il faut au moins avoir les valeurs 3 et 5 -- premiers premiers impairs
- P[0] = 3; P[1] = 9;
- P[2] = 5; P[3] = 10;
- P[4] = 7; P[5] = 14;
-
- printf("Liste des %d premiers nombres premiers\n 2 - 3 - 5 - 7 ", MAXPILE);
-
- MAXPILE -= 2;
-
- while (n < MAXPILE)
- {
- c = P[0];
- b = P[1];
- a = b+c;
-
- if (a >= P[3])
- {
- for (k=1; k<=n; k++)
- {
- P[2*(k-1)] = P[2*k];
- P[2*(k-1)+1] = P[2*k+1];
- if (a <= P[2*(k+1) + 1])
- {
- P[2*k] = c;
- P[2*k+1] = a;
- break;
- }
- }
- }
- i = (b+1) | 1;
-
- b = P[1];
- c = P[2*n+1];
-
- for (; i<b; i+=2)
- {
- if (i!=c)
- {
- n++;
- P[2*n] = i;
- P[2*n+1] = 2*i;
- printf("- %d ", i);
- }
- }
- }
- }
/* **************************************************** */
/* Erat.C */
/* **************************************************** */
/* Affichage des N premiers premiers */
/* **************************************************** */
/* (c) BZRD - 2006 */
/* **************************************************** */
#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
unsigned long *P;
/*
// Pour afficher le contenu du buffer, éventuellement (ce qui explique que P soit en globale)
void dumpPile(char *msg, int n)
{
int i;
printf("%s -- ", msg);
n = 2*n + 4;
for (i=n-1; i>=0; i--)
printf("%d ", P[i]);
printf("\n");
}
*/
void main(int argc, char **argv)
{
unsigned long n = 2;
unsigned long a,b,c;
unsigned long k, i;
unsigned long MAXPILE = 100;
if (argc > 1)
MAXPILE = atoi(argv[1]);
P = (unsigned long *)malloc(2*MAXPILE*sizeof(unsigned long));
// Il faut au moins avoir les valeurs 3 et 5 -- premiers premiers impairs
P[0] = 3; P[1] = 9;
P[2] = 5; P[3] = 10;
P[4] = 7; P[5] = 14;
printf("Liste des %d premiers nombres premiers\n 2 - 3 - 5 - 7 ", MAXPILE);
MAXPILE -= 2;
while (n < MAXPILE)
{
c = P[0];
b = P[1];
a = b+c;
if (a >= P[3])
{
for (k=1; k<=n; k++)
{
P[2*(k-1)] = P[2*k];
P[2*(k-1)+1] = P[2*k+1];
if (a <= P[2*(k+1) + 1])
{
P[2*k] = c;
P[2*k+1] = a;
break;
}
}
}
i = (b+1) | 1;
b = P[1];
c = P[2*n+1];
for (; i<b; i+=2)
{
if (i!=c)
{
n++;
P[2*n] = i;
P[2*n+1] = 2*i;
printf("- %d ", i);
}
}
}
}
 Conclusion
Si ça interesse quelqu'un j'essaierai de commenter.
Limitation à 2^31 pour les nombres affichés, mais ça dépend de toute façon de votre mémoire : pour afficher les N premiers nombres,
j'alloue un tableau de 2N longs.
Et puis, pour exploser mémoire et capacité de calcul, il vous faudra quand même être patient !
Affichage avec Erat 100 :
2 - 3 - 5 - 7 - 11 - 13 - 17 - 19 - 23 - 29 - 31 - 37 - 41 - 43 - 47 - 53 - 59 - 61 - 67 - 71 - 73 - 79 - 83 - 89 -
97 - 101 - 103 - 107 - 109 - 113 - 127 - 131 - 137 - 139 - 149 - 151 - 157 - 163 - 167 - 173 - 179 - 181 - 191 -
193 - 197 - 199 - 211 - 223 - 227 - 229 - 233 - 239 - 241 - 251 - 257 - 263 - 269 - 271 - 277 - 281 - 283 - 293 -
307 - 311 - 313 - 317 - 331 - 337 - 347 - 349 - 353 - 359 - 367 - 373 - 379 - 383 - 389 - 397 - 401 - 409 - 419 -
421 - 431 - 433 - 439 - 443 - 449 - 457 - 461 - 463 - 467 - 479 - 487 - 491 - 499 - 503 - 509 - 521 - 523 - 541
 Historique
- 13 octobre 2006 17:28:28 :
- Modification de mots clés !
 Sources du même auteur
 Sources de la même categorie
 Commentaires et avis
 Discussions en rapport avec ce code source dans le forum
une aide pour écrire un algo et un prog sur le nbr premiers [ par Julius Caesar ]
Bonjour, je n'arrive pas écrire l'algo et le prog de ce sujet:"Ecrivez un algo et un prog, qui affiche les nbrs premiers inferieurs à un entier n (ave
Supprimer les n premiers octet d'un fichier [ par arc59 ]
Bonjour, dans mon programme de modification des ID 3 tag, je voudrai permettre à l'utilisateur de supprimer les Id3tag de version 2. Ces tag sont plac
Découpage de n premiers caractères d'une chaine [ par Guidelor ]
BonjourJ'ai une chaine1 ="aaaaaaaaa123456"J'aimerais enlever "aaaaaaaaa"comment faire sachant que ce que je ve enlever est situé entre le 1er et le 10
Mes premiers pas sous linux sniff je suis ému [ par asmanur ]
Alors voila je me suis mis à la prog sous linux et j'ai quelqes prob & questions - quand je tape g++ main.cpp il me met qu'il ne conait pas g++ -quan
Premiers pas avec visual c++ express edition... [ par gdpasmini ]
Hello ! je débute avec visual c++ express edition, ma question va peut etre sembler stupide. J'ai créé un nouveau projet "windows form application".
Nombres premiers en C Urgent [ par maxfrancky ]
il me faut réaliser un programme permettant de lister les n premier nombres premier n utilisnat une liste chainée de structure contenant le nombre pre
factorial factors [ par brahimhakkou ]
svp aidez moi c urgentin this problem we want to determine the maximum number of integer terms (excluding1) that can be used to express n! par exemple
affichage 3 premiers caractere [ par OTHKREEN ]
<td id="HB_Focus_Element" valign="top" width="100%" b
Probleme de tri [ par bebeesther ]
Si tu peux m'aider, je serai tres reconnaissant!!!!!!!!Merci d'avance.
Nombres premiers... corrigez moi svp =3 [ par nisso13 ]
Salut, voila je m'explique, je voudrais faire un programme qui me liste les nombres premiers inferieurs à 1000... je l'ai fait mais il a une erreur qu
|
Derniers Blogs
 L'INTERFACE NATURELLE DE WINDOWS PHONE 7 SERIESL'INTERFACE NATURELLE DE WINDOWS PHONE 7 SERIES par odewit
La tendance est aux interfaces naturelles (NUI), et le keynote de Bill Buxton au MIX l'a bien souligné.
La charte graphique et ergonomique de Windows Phone 7 a donc été entièrement repensée en vue d'obtenir un maximum d'efficacité sur ce point. En re...
Cliquez pour lire la suite de l'article par odewit COMMENT MAPPER UNE VUE SQL SUR UNE COLLECTION DE COMPLEX TYPE?COMMENT MAPPER UNE VUE SQL SUR UNE COLLECTION DE COMPLEX TYPE? par Matthieu MEZIL
Avec EF, les vues doivent être mappées sur des entity types. Le problème c'est que les entity types doivent avoir une clé. Avec EF, nous avons les complex type qui n'ont pas de clé mais les vues ne peuvent pas être mappées dessus. Avec EF4, il est possibl...
Cliquez pour lire la suite de l'article par Matthieu MEZIL [WF4] UN BINDING ACTIVITY/ACTIVITYDESIGNER QUI PASSE MAL?[WF4] UN BINDING ACTIVITY/ACTIVITYDESIGNER QUI PASSE MAL? par JeremyJeanson
Certain d'entre vous on peut être vécu cette situation embarrassante après quelques temps passer avec WF4 : Au début avec mon " ActivityDesigner" , tout allait bien. Et puis un jour j'ai au des problèmes de " Binding" . Alors nous sommes allé sur le site ...
Cliquez pour lire la suite de l'article par JeremyJeanson
Forum
 TRADAIONTRADAION par shootangel
Cliquez pour lire la suite par shootangel
Logiciels
 Academy System (10.9.4.0)ACADEMY SYSTEM (10.9.4.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Xilisoft Convertisseur Vidéo Ultimate (5.1.39.0305)XILISOFT CONVERTISSEUR VIDéO ULTIMATE (5.1.39.0305)Xilisoft Convertisseur Vidéo Ultimate est un outil puissant de conversion vidéo, facile à utilise... Cliquez pour télécharger Xilisoft Convertisseur Vidéo Ultimate Xilisoft DVD Ripper Ultimate (5.0.64.0304)XILISOFT DVD RIPPER ULTIMATE (5.0.64.0304)Xilisoft DVD Ripper Ultimate est un logiciel excellent pour copier et convertir DVD vers presque ... Cliquez pour télécharger Xilisoft DVD Ripper Ultimate Rigs of Rods (63.3)RIGS OF RODS (63.3)c'est un jeu de multi-simulation camions,autobus voitures, avions, bateaux, hélicoptère avec défo... Cliquez pour télécharger Rigs of Rods
|