Trouver tout les nombres premiers

Commenter

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

S'inscrire maintenant

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.

Du même auteur (MeltedMind)