Trouver tout les nombres premiers

Soyez le premier à donner votre avis sur cette source.

Snippet vu 5 716 fois - Téléchargée 38 fois

Contenu du snippet

Trouver tout les nombres premiers est une grosse job de bras pour les ordinateurs, aucune autre methode que d'essayer de diviser un nombre potentiellement candidat par tout les nombre premiers qui lui sont inférieur.
Par contre quelques règles nous permettent d'éliminer des cas
1-tout les nombres pairs sont invalides (en fait on devrait compter par 6 et esssayer alors val-1 et val+1 comme un autre algorythme que l'on trouve sur CPPFrance)
2-si on a essayé de diviser A avec tout les nombres premier inférieur a B on sait qu'aucun nombre premier plus grand que A/B ne peut fonctionner (donc on essaie par les possibilité s'élimine par les deux bouts)
3-Les poissons rouges ne sont pas rouges mais plutôt Orange, c'est un fait.

23 août 2002,
j'ai optimisé un peu l'algorythme et j'ai aussi ajouté une fonction pour baisser la priorité du process. Cette dernière fonction est en commentaire mais si vous voulez sortir tous les nombres premiers jusqu'à 1000000000 il vaut mieux que je ne gèle pas toutes vos resssources pendant un mois. Donc si vous avez besoin de nombres premiers très grands (pratique uniquement en cryptage) lâchez vous lousse.

Source / Exemple :


#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <iostream.h>
#include <fstream.h>
#include <conio.h>
#include <stdlib.h>
#include <Windows.h>
void CreerFichierNombrePremier(int Nombre);
void LireNombre(void);

#define NombreDeNombrePremier 10000000

//jusqu'a 100millions le nombre de nombres premiers est inférieur à 6000000
//idéalement on devrait remplacé ces globales là par un tableau dynamique...
unsigned int VectPremier[NombreDeNombrePremier];
unsigned int Chaine[10];
unsigned int Chaine2[10];

int main(int argc, char* argv[])
{
   char choix = ' ';
   cout << "S = Sortir, C = Creer fichier de nombre premier" << endl;
   while (choix != 's' && choix != 'S')
   {
      choix = _getch();
      switch (choix)
      {
         case 'C':
         case 'c':
         {
            //attention 100 000 000 c'est vraiement long... 
            CreerFichierNombrePremier(NombreDeNombrePremier);
            cout << "termine" << endl;
            cout << "S = Sortir, C = Creer fichier" << endl;
            break;
         }

         case 'S':
         case 's':
         {
            break;
         }
         
         default:
         {
            cout << "Votre choix est invalide"<< endl;
            cout << "S = Sortir, C = Creer fichier"<< endl;
         }   
      }
   }
      return 0;
}

void CreerFichierNombrePremier(int Nombre)
{
   double NombreATester = 0;
   int NombreTemp = 0;
   int PlusGrandTest = 0;
   double PlusPetitTest = 0;
   double Comparateur = 0;
   bool Premier = false;
//   int i = 1;
   int iTotal = 2;
   int j = 0;
   int Compteur = 1;
   bool alternateur = false;
   
   ofstream NombrePremier("c:\\temp\\NombrePremier_2.txt");
         
   VectPremier[0] = 2;
   VectPremier[1] = 3;
   NombrePremier << VectPremier[0] << '\t' << VectPremier[1] << '\t';
   
   long Start;
   time(&Start);
   long End ;
   /*
   SetPriorityClass(
  GetCurrentProcess(),        // handle to process
  IDLE_PRIORITY_CLASS   // priority class
);

  • /
//Boucle optimisé... on incrémente par la fin avec Alternateur //on commence à 5 et on incrémente respectivement de 4 puis de 2 //ce qui revient à utiliser la règle "on incrémente de 6 et on //regarde la valeur -1 puis la valeur +1 for (NombreATester = 5;iTotal < Nombre;) { PlusGrandTest = (int)NombreATester; Premier = true; for (j = 0;PlusPetitTest <= PlusGrandTest;j++) { PlusPetitTest = VectPremier[j]; PlusGrandTest =(int)(NombreATester /PlusPetitTest); Comparateur = (float) NombreATester /PlusPetitTest; //si l'équation donne un résultat entier le float et le int vont avoir la meme valeur if(PlusGrandTest == Comparateur) { //on force la sortie de la boucle //ce n'est pas un nombre premier PlusPetitTest =(float) PlusGrandTest; Premier = false; } } //si le nombre courant est effectivement un nombre premier if(Premier) { NombreTemp = (int)NombreATester; VectPremier[iTotal] = NombreTemp; NombrePremier << NombreTemp; if(iTotal%5 == 4) { NombrePremier << endl; } else { NombrePremier << "\t"; } PlusPetitTest = 2; iTotal++; /*if(iTotal%100000 == 0){ printf("%d\n",iTotal);// <<"\n";// un autre million de fait\n"; }*/ } if(alternateur) { NombreATester += 4; alternateur = false; } else{ NombreATester +=2; alternateur = true; } } time(&End); NombrePremier << "\nNomber " << iTotal<< " Temps " << End - Start; }

Conclusion :


Je crois qu'il marche particulièrement bien
tout les nombre premier se retrouve dans un fichier (c:\temp\NombrePremier.txt)
les buffer sont global (ordinaire) de grandeur fixe (poche je sais je sais)
vous devez tapez dans le code le nombre de nombre premier que vous voulez

A voir également

Ajouter un commentaire Commentaires
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

mdr :-) void main, gcc l'accepte même plus, il te crache au visage quand tu écris ça ;-) j'ai un bouquin qui se décrit comme "le livre pour passer proprement du C au C++", et ils mettent void main partout, c'est pas possible O_o

je vias analyser ce code de prêt, j'ai besoin d'un programme très rapide pour créer la liste des nombres premiers inférieurs à un nombre de l'ordre de 10 000 000. ça peut pas prendre plus d'une demi seconde, alors gloups quoi ^^
Messages postés
35
Date d'inscription
mardi 8 janvier 2002
Statut
Membre
Dernière intervention
6 janvier 2003

int main(int argc, char* argv[]) est LE standart en dos,
pour ma part il arrive souvent que j'utilise directement ces paramètres.
Messages postés
7
Date d'inscription
jeudi 19 décembre 2002
Statut
Membre
Dernière intervention
19 mars 2003

NerOcrO : int main(void) est dans la norme et est meme conseillé. void main(void) est une horreur sans nom, totalement interdite par la norme.
Messages postés
33
Date d'inscription
mardi 10 octobre 2000
Statut
Membre
Dernière intervention
27 mai 2004

Mieux vaut utiliser ça :
void main (void)
{
...
sans de "return 0;"
}
Messages postés
33
Date d'inscription
mardi 10 octobre 2000
Statut
Membre
Dernière intervention
27 mai 2004

C'est pas mal du tout mais ce n'est pas la peine d'utiliser a structure suivnate :
int main(int argc, char* argv[])
{
...

}

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.