Test de primalité A: Méthodes simples

Télécharger le projet
Commenter

Description

Bonjour,

Un test de primalité est un algorithme qui permet de savoir si un nombre entier positif est premier.
Cette première série de fonctions se limite aux entiers sur 32 bits.

Méthodes simples

Pour tester la primalité d'un nombre N, on vérifie si ce nombre n'est divisible par aucun des nombres compris entre 2 et N-1. 
bool isPrimeA0(uint N) { // très mauvais !!!
  if (N<=1) return false;
  for (uint i=2; i<N; ++i) if (N%i==0) return false;
  return true;
} // n'utilisez pas ce code !!!
N'utilisez pas ce code car il est très lent !

L'amélioration la plus pertinente est de ne parcourir les éventuels diviseurs que jusqu'à la racine carrée de N: 
bool isPrimeA1(uint N) {
  if (N<=1) return false;
  uint n=sqrt(N);
  for (uint i=2; i<=n; ++i) if (N%i==0) return false;
  return true;
}


Nous pouvons encore ne traiter que les nombres impairs: 
bool isPrimeA2(uint N) {
  if (N<=2) return (N<2) ? false : true;
  if (N%2==0) return false; // pair
  uint n=sqrt(N);
  for (uint i=3; i<=n; i+=2) if (N%i==0) return false;
  return true;
}

Méthode avec liste de nombres premiers

Utilisons maintenant une liste lst de nombres premiers <= √N.
Elle sera calculée avec PrimeList contenue dans le fichier PrimeList.cpp.
Comme le montre CodeS-SourceS: Nombres premiers: PrimeList, l'instruction
lst=PrimeList(65535, &np);
prend moins d'une milliseconde et permet de traiter l'ensemble des entiers 32 bits: 
uint np, lst=PrimeList(65535, &np); // pour N 32 bits

bool isPrimeA3(uint N, uint *lst) { // lst = [2,3,5,7,11,17,...,(uint)√N,...]
  if (N<=1) return false;
  uint n=sqrt(N), p, i=0;
  while ((p=lst[i++])<=n) if (N%p==0) return false;
  return true;
}

Temps d'exécution

Le programme PrimA.cpp donne le résultat suivant: 
Tests de primalité:

isPrimeA0: (100000 nombres entre 0 et 65535)
  np = 10030; 1032 ms.
isPrimeA0: (12 nombres entre 0 et 4294967295)
  np = 1; 3016 ms.
isPrimeA1: (1000000 nombres entre 0 et 65535)
  np = 99600; 98 ms.
isPrimeA1: (100000 nombres entre 0 et 4294967295)
  np = 4739; 938 ms.
isPrimeA2: (1000000 nombres entre 0 et 65535)
  np = 99600; 52 ms.
isPrimeA2: (100000 nombres entre 0 et 4294967295)
  np = 4739; 468 ms.
isPrimeA3: (1000000 nombres entre 0 et 65535)
  np =  99600; 43 ms.
isPrimeA3: (100000 nombres entre 0 et 4294967295)
  np = 4739; 102 ms.

Premières conclusions

Comme annoncé, isPrimeA0 est très mauvais: ne l'utilisez pas !

L'amélioration des trois codes suivants est fulgurante.
En ne traitant que les nombres impairs, le temps est quasiment divisé par deux.

Ne considérer que les diviseurs premiers s'avère avantageux, surtout pour de grands nombres.

Certains liens ci-dessous nous montrent qu'il existe des algorithmes encore bien plus efficaces.
Quelques'uns seront abordés prochainement.

Liens:
Nombres premiers
WikipédiA: Nombre premier
WikipédiA: Test de primalité
Nombres PREMIERS: Recherche de PRIMALITÉ
CodeS-SourceS: Premiers (pgl10)

Bonne lecture ...
Télécharger le projet

Codes Sources

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 (William VOIROL)