Nombres premiers jumeaux: A-méthode classique

Télécharger le projet
Commenter

Description

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 ...
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 (William VOIROL)