Tester si un nombre est premier

Calcul de nombres premiers

Petit test de primalité d'un unsigned long long int (sur x86 archi 32bits cela donne un nombre entre 0 et 18446744073709551616). Un exemple de code sera posté, utilisant la librairie gmp pour des nombres plus grands.

Nous utilisons ici la méthode dite "naïve" qui conciste à calculer les modulos successifs de tous les nombres impairs de 3 à la racine du nombre en question, après avoir testé si le nombre est divisible par 2.

#include <stdio.h>
#include <math.h>
 
unsigned long long int primeTest(unsigned long long int nb){
    unsigned long long int racine = (unsigned long long int)(sqrt(nb))+1;
    unsigned long long int i;
    if(nb == 1){
            return 1;
    }
    if((nb % 2) == 0) {
        return 2;
    }
    for (i = 3 ; i < racine ; i+=2){
        if((nb %i) == 0){
            return i;
        }
    }
    return 0;
}
 
int main(void){
    unsigned long long int nb = 3151468321657; 
    unsigned long long int diviseur;
    if((diviseur = primeTest(nb)) == 0){
        printf("Le nombre %lld est premier\n",nb);
    }else{
            printf("Le nombre %lld est divisible par %lld\n", nb, diviseur);
    }
    return 0;
}

A compiler avec la librairie math (-lm) par exemple :

gcc -Wall -lm test.c -o prog -std=gnu99
Domaine: