Bonjour,
Deux nombres premiers sont dits jumeaux (en: twin primes, de: Primzahlzwillinge) lorsqu'ils ne diffèrent que de 2.
Voici la suite des premiers couples de nombres premiers jumeaux:
(3,5) (5,7) (11,13) (17,19) (29,31) (41,43) (59,61) (71,73) (101,103) (107,109) (137,139) ...
Selon la méthode "classique", pour déterminer le début de la liste des couples de nombres premiers jumeaux, on calcule d'abord une liste de nombres premiers, puis on en extrait les couples formés de jumeaux.
Voir aussi
WikipédiA: Nombres premiers jumeaux.
Fonction "classique"
Un "mauvais" exemple trouvé sur le web peut ressembler à:
int nP,prm[10000];
void PrimList(int N) {
nP=0;
for (int n=3; n<N; n++) {
int c=0;
for (int j=2; j<n; j++)
if (n%j==0) c++;
if (c==0) {prm[nP]=n; nP++;}
}
}
/*
N=100000, nP=9591, twin primes:
(3,5) (5,7) (11,13) (17,19) (29,31)
(41,43) (59,61) (71,73) (101,103) (107,109)
(137,139) (149,151) (179,181) (191,193) (197,199)
...
(98729,98731) (98807,98809) (98867,98869) (98897,98899) (98909,98911)
(98927,98929) (99131,99133) (99137,99139) (99257,99259) (99347,99349)
(99527,99529) (99707,99709) (99719,99721) (99989,99991)
Number of twins: 1224; time: 16231 ms
*/
Comme il ne faut "que" 161 ms pour déterminer la liste des 205 jumeaux formés de nombres premiers jusqu'à 10000, ce code peut même passer pour "assez bon" avec cet exemple de calcul.
Première amélioration
Dans la boucle extérieure, on incrémente
n de 2:
n+=2.
En effet, à part 2, il n'existe aucun nombre premier pair:
int nP,prm[10000];
void PrimList(int N) {
nP=0;
for (int n=3; n<N; n+=2) {
int c=0;
for (int j=2; j<n; j++)
if (n%j==0) c++;
if (c==0) {prm[nP]=n; nP++;}
}
}
/*
N=100000, nP=9591, twin primes:
(3,5) (5,7) (11,13) (17,19) (29,31)
(41,43) (59,61) (71,73) (101,103) (107,109)
(137,139) (149,151) (179,181) (191,193) (197,199)
...
(98729,98731) (98807,98809) (98867,98869) (98897,98899) (98909,98911)
(98927,98929) (99131,99133) (99137,99139) (99257,99259) (99347,99349)
(99527,99529) (99707,99709) (99719,99721) (99989,99991)
Number of twins: 1224; time: 8341 ms
*/
Le temps d'exécution est quasiment divisé par deux !
Deuxième amélioration
Dès qu'on a trouvé un diviseur, on peut sortir de la boucle intérieure:
int nP,prm[10000];
void PrimList(int N) {
nP=0;
for (int n=3; n<N; n+=2) {
int c=0;
for (int j=2; j<n; j++)
if (n%j==0) {c=1; break;}
if (c==0) {prm[nP]=n; nP++;}
}
}
/*
N=100000, nP=9591, twin primes:
(3,5) (5,7) (11,13) (17,19) (29,31)
(41,43) (59,61) (71,73) (101,103) (107,109)
(137,139) (149,151) (179,181) (191,193) (197,199)
...
(98729,98731) (98807,98809) (98867,98869) (98897,98899) (98909,98911)
(98927,98929) (99131,99133) (99137,99139) (99257,99259) (99347,99349)
(99527,99529) (99707,99709) (99719,99721) (99989,99991)
Number of twins: 1224; time: 1514 ms
*/
L'amélioration du temps d'exécution est intéressante: on passe à 1514 millisecondes !
Troisième amélioration
Dans la boucle intérieure, on remplace le test
j<n par
j*j<=n.
Effectivement,
j ne peut diviser
n que si
j<=√n (ou
j²<=n):
int nP,prm[10000];
void PrimList(int N) {
nP=0;
for (int n=3; n<N; n+=2) {
bool isPrim=true;
for (int j=2; j*j<=n; j++)
if (n%j==0) {isPrim=false; break;}
if (isPrim) prm[nP++]=n;
}
}
/*
N=100000, nP=9591, twin primes:
(3,5) (5,7) (11,13) (17,19) (29,31)
(41,43) (59,61) (71,73) (101,103) (107,109)
(137,139) (149,151) (179,181) (191,193) (197,199)
...
(98729,98731) (98807,98809) (98867,98869) (98897,98899) (98909,98911)
(98927,98929) (99131,99133) (99137,99139) (99257,99259) (99347,99349)
(99527,99529) (99707,99709) (99719,99721) (99989,99991)
Number of twins: 1224; time: 10 ms
*/
L'amélioration du temps d'exécution est remarquable: on passe à 10 millisecondes !
Quatrième amélioration
Adaptons la fonction
PrimeList de
CodeS-SourceS: Nombres premiers: PrimeList:
int nP,prm[10000];
void PrimList(int N) {
int E=(N+1)/2;
nP=0;
unsigned char *usv=(unsigned char*)malloc(E),*usv_i;
memset(usv,1,E);
for (int i=1,e=3; e<=N; ++i,e+=2) if (*(usv_i=usv+i))
for (int j=(N/e-1)/2; j>=i; --j) if (usv[j]) usv_i[e*j]=0;
for (int e=1; e<E; ++e) if (usv[e]) prm[nP++]=(e<<1)|1;
free(usv);
}
/*
N=100000, nP=9591, twin primes:
(3,5) (5,7) (11,13) (17,19) (29,31)
(41,43) (59,61) (71,73) (101,103) (107,109)
(137,139) (149,151) (179,181) (191,193) (197,199)
...
(98729,98731) (98807,98809) (98867,98869) (98897,98899) (98909,98911)
(98927,98929) (99131,99133) (99137,99139) (99257,99259) (99347,99349)
(99527,99529) (99707,99709) (99719,99721) (99989,99991)
Number of twins: 1224; time: 1 ms
*/
Le temps d'exécution est encore divisé par 10 !
Premières conclusions
Avec les quatre améliorations ci-dessus,
le temps d'exécution est divisé par 16000 !
Et ce rapport devrait encore s'agrandir en augmentant la taille de la liste.
Comme on n'a pas encore utilisé les caractéristiques spécifiques aux nombres premiers jumeaux, il reste de la matière pour un prochain article
Nombres premiers jumeaux: B-....
Le
zip contient le fichier
JumeauxA.cpp avec un programme testant la dernière amélioration.
Pour les moins bonnes solutions, remplacez la fonction
PrimList correspondante.
Le résultat se trouve dans le fichier
Output.txt.
Bonne lecture ...
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.