Nombres premiers

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

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)