Nombres premiers 18446744073709551557

Soyez le premier à donner votre avis sur cette source.

Vue 1 331 fois - Téléchargée 20 fois

Description

/*
Moins de 30 secondes pour savoir si un nombre de 64 bits est premier
sinon décomposition en produit de facteurs premiers
Nombre maxi : 18446744073709551557

*/
#include<iostream>
#include<math.h>
#include<omp.h>

using namespace std;

typedef unsigned long long ull;

class prim;
prim*P[100];//les facteurs (class prim)
int nb;//nombre de facteurs différents

class prim
{
 ull z;//nombre
 int e;//exposant
 public:
 prim(ull x)
 {
  z=x;
  e=1;
 }
 void inc(){e++;}
 ull getz(){return z;}
 int gete(){return e;}
 void aff(){cout<<z;if(e>1)cout<<"^"<<e;}
};

void add(ull x)
{
 for(int n=0;n<nb;n++)
 {
  if(P[n]->getz()==x)
  {
   P[n]->inc();
   return;
  }
 }
 P[nb++]=new prim(x);
}

ull parseint(char*s)
{
 ull i=0;
 s--;
 while(*++s)
 {
  ull v=i;
  if((*s>='0')&&(*s<='9'))
  {
   i=i*10+(*s-48);
   if(i<v){i=v;cout<<" > 2^64-1nn";}
  }
  else cout<<"Erreur dans la ligne de commanden";
 } 
 return i;
}
//ull k=0;
ull modulo(ull n)
{
 if((n%2)==0) return 2;
 if((n%3)==0) return 3;
 if((n%5)==0) return 5;
  if((n%7)==0) return 7;
  ull a, p = 1 ;
  ull q=(sqrt(n)+1)/6;
  while(++p<=q)
  {
   a=6*p;
   if((n%(a-1))==0)return a-1 ;
   if((n%(a+1))==0)return a+1 ;
  }
 return n;//k?k:n;
}

void facteurs(ull n)
{
 ull tmp = modulo(n) ;
 if(tmp<n)facteurs(n / tmp);
 add(tmp);
}

int main(int argc,char*argv[])
{
 ull n ;
 if(argc>=2)n=parseint(argv[1]);
 else n=18446744073709551557u;
 cout << "prim.exe nombre (18446744073709551557 premier 18446744073709551615 non premier)nn" ;
 if(n<2)
 {
  cout << n << " n'est pas premiernn" ;
  return 0;
 }
 cout << "Patienter 30 secondes svpnn";
 ull r=modulo(n);
 if(n==r)
  cout << n << " est premiern" ;
 else
 {
  cout << n << " =";
  facteurs(r) ;
  facteurs(n/r) ;
  for(int n=0;n<nb-1;n++)//tri des facteurs
   for(int i=n+1;i<nb;i++)
   {
    if(P[i]->getz()<P[n]->getz())
    {
     prim*w=P[i];
     P[i]=P[n];
     P[n]=w;
    }
   }
  for(int n=0;n<nb;n++)
  {
   if(n)cout << " .";
   cout<<" ";
   P[n]->aff();
   delete P[n];
  }
 }
 return 0;
}

Codes Sources

A voir également

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.