Soyez le premier à donner votre avis sur cette source.
Vue 2 590 fois - Téléchargée 193 fois
#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; }
Merci pour ce code intéressant !
Il m'a inspiré une "prolongation".
Pour vérifier la primalité d'un int on peut utiliser la fonction suivante très simple :
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.
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.