Premiers

Télécharger le projet
Commenter

Description

Les nombres premiers sont un domaine universel, public et gratuit que l'on a déjà largement exploré mais qui peut toujours être l'objet de nouvelles découvertes. En raison du caractère irrégulier et presque imprévisible de la suite des nombres premiers il est amusant ou même intrigant d'y rechercher toutes sortes de constatations très variées.

La méthode du crible d'Ératosthène permet de calculer facilement les nombres premiers jusqu'à un nombre entier donné. Cependant en raison de la mémoire nécessaire et du temps d'exécution cette méthode est limitée. Il est bien difficile d'aller plus loin que 300 milliards. Avec la méthode du crible segmenté d'Ératosthène on peut aller plus loin et plus vite, mais on est toujours limité.

Si on souhaite ou si on a besoin d'une exploration plus vaste il faut utiliser les méthodes adaptées à chaque objectif. Les questions habituelles les plus basiques à traiter sont les suivantes.
1°) Est-ce que un nombre donné est premier ou composé ?
2°) Quel est le premier nombre premier qui suit un nombre donné ?
3°) Quel est le nombre de nombres premiers jusqu'à un nombre donné ?
4°) Quel est le n-ième nombre premier ?

Dans le programme ci-joint on ne s'occuppe uniquement que des deux premières questions. Pour un critère de primalité d'un entier donné on utilise la méthode de Miller & Rabin. C'est une méthode probabiliste. Si elle décide que le nombre étudié est composé, c'est mathématiquement exact. Par contre, si elle décide que le nombre étudié est premier, c'est très probablement exact. Il peut arriver, rarement, qu'un nombre composé soit détecté en tant que nombre premier, mais la probabilité de ce résultat erroné est gérable et peut être prévue aussi petite que l'on veut. En pratique 12 témoins de Miller qui évitent le caractère composé du nombre étudié suffisent pour déclarer que ce nombre est très probablement premier, c'est à dire premier en pratique.

Pour calculer le premier nombre premier qui suit un nombre donné on parcourt les entiers qui le suivent en évitant les multiples de 2, 3, 5 et 7 et en utilisant le critère de primalité de Miller & Rabin pour chacun d'eux. Cette méthode simple a une bonne performance. Mais il serait tout a fait inadapté de calculer le n-ième nombre premier de cette façon : la performance serait catastrophique. Pour ce problème il faut trouver d'abord une bonne approximation du nombre recherché et seulement terminer en explorant les entiers qui suivent.

Les plus grands entiers représentés sur 8 octets, ou 64 bits, ont jusqu'à 19 chiffres décimaux. Avec les méthodes décrites on peut calculer le premier nombre premier qui suit tout entier de type int64_t en moins que quelques milisecondes. Si on veut aller au delà de la limite des int64_t on utilisera une bibliothèque comme GMP, MPIR, NTL ou autre, dans laquelle les fonctions équivalentes sont déjà proposées et optimisées. Pour avoir ici un temps d'exécution fiable on fait le même calcul 1000 fois.

Source : 

/**********************************************************
*      Programme Primes   -    @author pgl10              *
*  Primalité de Miller & Rabin et nombre premier suivant  *
**********************************************************/

// exponentiation modulaire : expmod(n, p, m) = n^p mod(m)
int64_t expmod(int64_t n, int64_t p, int64_t m) {
    int64_t res = 1;
    while(p > 0) {
        // Si (p % 2) > 0 
        if(p & 1) res = mulmod(res, n, m);
        // p = p / 2 
        p = p >> 1;
        n = mulmod(n, n, m);
    }
    return res;
}

// Pour le test de primalité de Miller & Rabin
// true si c'est incertain : n est peut-être premier
// false si a est un témoin de Miller : n est composé
bool rabin(int64_t n, int64_t d, int64_t a) {
    int64_t nm1 = n - 1;
    int64_t p = expmod(a, d, n);
    if(p == 1 || p == nm1) return true;
    while(d != nm1) {
        p = expmod(p, 2, n);
        if(p == nm1) return true;
        if(p == 1) return false;
        d = 2 * d;
    }
    return false;
}

// Test de primalité de Miller & Rabin
// si is_prime(n) est true : n est très probablement premier
// si is_prime(n) est false : n est mathématiquement composé
bool is_prime(int64_t n) {
    if(n == 2 || n == 3) return true;
    if(n <= 1 || n == 4) return false;
    // maintenant n > 4
    int64_t nm1 = n - 1;
    int64_t d = nm1;
    // pour : n = 2^x * d + 1 
    while(d == (d/2)*2) d = d / 2;
    // Après 12 essais n est un premier très probable
    for(int32_t i=0; i<12; i++) {
        int64_t a = randbi(1, nm1);
        if(!rabin(n, d, a)) return false;
    }
    return true;
}

// calcul du nombre premier qui suit l'entier x
int64_t next_prime(int64_t x) {
    // On va contrôler les nombres plus grands que x
    // dans la liste des 47 premiers nombres premiers
    // puis en continuant par les entiers suivants
    // en évitant les multiples de 2, 3, 5 et 7
    int prems[47] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,
                     67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,
                     139,149,151,157,163,167,173,179,181,191,193,197,199,211};
    if(x < 2) return 2;
    if(x < prems[46]) for(int i=0; i < 46; i++) if(x < prems[i+1]) return prems[i+1];
    // Dans la liste des entiers sans les multiples 
    // de 2, 3, 5 et 7 il y a un cycle de longueur 210
    // ayant 48 nombres dont voici la première liste :
    // 211+{221,223,227,229,233,239,...,401,403,407,409,419,421}
    // A noter que après 421 : 221+210=431=421+(221-211)=421+10 
    // Dans ce cycle les écarts successifs sont :
    int suite[48] = {10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,
                     2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2};
    int64_t p = 1+(x/210)*210;
    // par exemple, si x = 420 : p = 421 est premier
    if(x < p) if(is_prime(p)) return p;
    // exploration du cycle où se trouve x et
    // éventuellement du ou des cycles suivants
    for(;;) {
        for(int i=0; i < 48; i++) {
            int64_t q = p + suite[i];
            if(x < q) if(is_prime(q)) return q;
            p = q;
        }
    }
}

Conclusion :

Merci pour vos commentaires
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 (pgl10)