TROUVER TOUT LES NOMBRES PREMIERS , Source N°9415

Information sur la source

Catégorie :Maths & Algorithmes Niveau : Débutant Date de création : 10/01/2002 Date de mise à jour : 23/08/2002 16:53:57 Vu : 3 238

Auteur : MeltedMind

Ecrire un message privé

Note :
Aucune note

Commentaire sur cette source (5)

Ajouter un commentaire et/ou une note

Description

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

#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;
}

#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

Sources du même auteur

Toutes les sources de MeltedMind

Sources de la même categorie

Toutes les sources de la catégorie Maths & Algorithmes

Commentaires

Commentaire de NerOcrO le 12/01/2002 11:51:49

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

}
Commentaire de NerOcrO le 12/01/2002 11:53:15

Mieux vaut utiliser ça :
void main (void)
{
...
sans de "return 0;"
}
Commentaire de Tamahome le 30/01/2003 23:55:39

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.
Commentaire de MeltedMind le 18/03/2003 16:01:56

int main(int argc, char* argv[]) est LE standart en dos,
pour ma part il arrive souvent que j'utilise directement ces paramètres.
Commentaire de Kirua le 25/12/2003 03:06:21

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 ^^