Nombres premiers

Soyez le premier à donner votre avis sur cette source.

Vue 945 fois - Téléchargée 78 fois

Télécharger le projet
Commenter

Description

Il y a des circonstances dans lesquelles la liste des premiers nombres premiers est nécessaire pour programmer le source que l'on souhaite. L'algorithme d'Ératosthène classique est une bonne méthode pour obtenir une liste d'indicateurs qui déterminent les nombres premiers parmi ceux qui sont référencés dans cette liste. Mais pour obtenir la liste des nnp premiers nombres premiers il faut un complément qui est un peu mal commode. C'est pourquoi il peut être intéressant de calculer directement la liste des nnp premiers nombres premiers même si la méthode n'est pas fondamentalement différente.

Le nombre maxi = INT_MAX = (2^31)-1 = 2147483647 est un nombre premier. Il a le rang de valeur ieme. C'est le plus grand nombre premier pour un entier de type int sur 4 octets. Et le nombre 46340 est le plus grand entier dont le carré est plus petit que le nombre maxi.

Pour nnp = 10 000 000 le temps de calcul est d'environ 45 secondes et pour nnp = 100 000 000 il est d'environ 20 minutes. Malgré le parcours des entiers effectué en évitant les multiples de 2, 3 et 5 on peut estimer que les performances obtenues ne sont pas exceptionnelles.

On écrit : mp[k]=mp[k]+2*j pour mettre à jour le prochain multiple utilisable de np[k] parce que j=np[k] est impair donc mp[k]=mp[k]+j serait pair et ne pourrait pas être rencontré dans la suite des explorations. Pour calculer correctement les grandes valeurs de np[i] il faut utiliser le type int64_t pour j parce que j*j dépasse le nombre maxi.

Source : 

#include <iostream>
#include <cstdint>
           
// Calcul des nnp premiers nombres premiers dans np[i],i=1,nnp
// Le tableau np doit avoir nnp+1 éléments. ( nnp > 3 )
void prems(int nnp, int* np) { 
    const int maxi = INT_MAX, ieme = 105097565;
    int m,n,s,t[]={4,2,4,2,4,6,2,6};
    int* mp;
    if(nnp<ieme) m = nnp+1;     // Le dernier np[i] sera calculé pour i=nnp.
    else m = ieme;              // Si nécessaire np[ieme] donné séparément.
    mp = new int[m];            // mp[] est un tabeau auxiliaire temporaire.
    np[0]=1;  np[1]=2;  np[2]=3;  np[3]=5;    np[4]=7;      // Les premiers
    mp[0]=1;  mp[1]=4;  mp[2]=9;  mp[3]=5*5;  mp[4]=7*7;    // sont donnés.
    int i = 5;                  // i est le rang du prochain nombre premier.
    s=0;                        // On va éviter les multiples de 2, 3 et 5
    for(n=11; i<m; n=n+t[s]) {  // 11 13 17 19 23 29 31 37 41 43 47 49 ...
        for(int k=4;;k++) {     // Le nombre n a-t-il un diviseur premier ?
            int64_t j = np[k];           // On commence à j = np[4] = 7
            if( n == mp[k] ) break;      // Si n est multiple de np[k]
            if( j*j > int64_t(n) ) {     // Si aucun np[k] n'a fourni
                np[i] = n;               // un diviseur de n, alors 
                if(n>46340) mp[i]=maxi;  // n est premier : on l'archive
                else mp[i] = n*n;        // et on initialise son prochain 
                i = i+1;                 // multiple utilisable ensuite.
                break;
            }
            if( n > mp[k] ) {      // mp[k] : prochain multiple de np[k]
                if( mp[k] > maxi-int(2*j) ) mp[k] = maxi;  
                else mp[k] = mp[k] + int(2*j);
            }
        }                                     
        if(++s == 8) s=0;
    }
    delete[] mp;   // pour libérer la mémoire du tableau auxiliaire mp[]
    if(nnp == ieme) np[ieme] = maxi;
}
        
int main() {
    int nnp=1234567;
    int* np = new int[nnp+1];
    prems(nnp, np);
    std::cout << std::endl;
    std::cout << "nnp : " << nnp << "   np[nnp] : " << np[nnp] << std::endl;
    std::cout << std::endl;
    return 0;
}

Conclusion

Ce code programmé avec Visual Studio Express 2012 pour Windows Desktop semble bien adapté pour calculer la liste des nnp premiers nombres premiers quelque soit nnp tel que 4 ≤ nnp ≤ ieme. Merci pour vos remarques et améliorations éventuelles.

Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Signaler
William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
 -
Bonjour pgl10,

Merci pour ce code intéressant !
Il m'a inspiré une "prolongation".
Signaler
Georges_46
Messages postés
1
Date d'inscription
mardi 12 mars 2019
Statut
Membre
Dernière intervention
15 mars 2019
 -
c'est intéressant moi je connais que deux façons de calculer les nombres premiers une méthode rapide et le crible d'erathostène
Signaler
pgl10
Messages postés
310
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
6 juillet 2019
 1 -
Bonjour,
Pour vérifier la primalité d'un int on peut utiliser la fonction suivante très simple : 

bool isprem(int n) {
    unsigned int t[]={4,2,4,2,4,6,2,6};
    if(n < 2) return false;
    if(n%2 == 0) return n==2;
    if(n%3 == 0) return n==3;
    if(n%5 == 0) return n==5;
    unsigned int m = n;
    unsigned int s = 7;
    for(unsigned int i=7; i*i<=m; i=i+t[s]) {
        if(m%i==0) return m==i;
        if(++s == 8) s=0;
    }
    return true;
}

Le contrôle de primalité de Miller et Rabin sous sa forme probabiliste ou même sous sa forme déterministe conviendrait aussi mais il est utilisé normalement pour des entiers de plus grande taille. Pour un entier de type int sur 4 octets ce code est bien suffisant.
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)