Calcul de nombres premiers (nombres doubles --> 1.7e308)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 4 944 fois - Téléchargée 35 fois

Contenu du snippet

Voici un code pour calculer les nombres premiers. Je sais qu'il existe déja beacoup de code qui font cela mais celui ci traite avec des double, on peux donc calculer les nombres premiers jusqu'a la limite du double (~1.7E308).
Les nombres peuvent être inscrits dans un fichier texte.

Au lieu de la traditionelle formule if(nombre%x == 0) on a une variable temp qui est égale a nombre/x ensuite on teste si temp est entier par la formul
if(temp - floor(temp) == 0). Mais c'est un peu plus long.

Source / Exemple :


// Par coockiesch, 16.02.03
#include <iostream>
#include <windows.h>
#include <cmath>
#include <fstream>

using namespace std;

bool EstPremier(double nb);

int main()
{
  double max;
  char choix = 'n';

  cout<<"Jusqu'a quel nombre voulez-vous recherche des nombres premiers? "<<endl;
  cin>>max;
  cout<<"Voulez-vous generer un fichier (ca rendra le calcul plus long) (o/n)? ";
  cin>>choix;
  cout<<"---------------------------------------------------------------"<<endl;

  if(choix == 'o' || choix == 'O')
  {
    double retour = 1.0, temp;
    ofstream out("Nombres premiers.txt");
    if(!out)
    {
      cout<<"Impossible d'écrire dans le fichier\n";
      system("pause");
      cout<<"\n";
    }
    for(double i = 2;i < max; i++)
    {
      if(EstPremier(i))
      {
        cout<<i<<endl;
        out << i << " ";
        ++retour;
        temp = retour / 10;
        if(temp - floor(temp) == 0)
          out<< "\n";
      }
    }
    out.close();
    cout<<"Fichier ecrit"<<endl;
  }
  else
  {
    for(double i = 2;i < max; i++)
    {
      if(EstPremier(i))
      {
        cout<<i<<endl;
      }
    }
  }
  system("pause");
}

bool EstPremier(double nb)
{
  double temp;

  if(nb == 2)
    return true;

  temp = nb/2;
  if(temp - floor(temp) == 0)
    return false;

  double i = 3.0;
  while(i*i <= nb)
  {
    temp = nb / i;
    if(temp - floor(temp) == 0)
      return false;
    i++;
  }
  return true;
}

A voir également

Ajouter un commentaire

Commentaires

scelw
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007
-
un an après : (j'espère qu'il n'est pas trop tard)

Pour manipuler des très grands nombres de manière exacte, il existe des librairies très utiles : GMP, NTL, etc. GMP est mondialement connue et très bien conçue mais l'aide est en anglais uniquement.
D'ailleurs si quelqu'un connaissait cette librairie, je voudrais bien qu'il m'aide (jojo29118@hotmail.com) !!!

Ces librairies permettent de manipuler des nombres de taille arbitraire (des millions de chiffres ou plus) ! C'est vraiment une mine d'or ! (et c'est d'autant plus dommage de ne pas pouvoir les utiliser faute d'aide conséquente en français...)
coockiesch
Messages postés
2268
Date d'inscription
mercredi 27 novembre 2002
Statut
Membre
Dernière intervention
13 septembre 2013
3 -
Merci. Et j'ai vu que des erreurs se produisent dès 1e6, des nombres pairs sont marqués premiers. Si quelqu'un a une autre facon de faire, ca m'intérêsse.
MetalDwarf
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006
-
Ca peut pas marcher!!! Tu crois que les double sont codes avec une precision de 308 chiffres???? Non c est 14 je crois et donc tes nombres plus grands seront des approximations comme avec une calculatrice!!! En plus la division c est lent...
cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2 -
Je ne suis abolument pas convaincu de l'efficacité du code. Certes on peut arriver à trancher sur la primalité de plus grands nombres mais l'opération de division montre alors toutes ces carences. Mieux vaut utiliser un algo plus complexe

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.