Nombres premiers: Crible segmenté (A)

Soyez le premier à donner votre avis sur cette source.

Vue 4 851 fois - Téléchargée 302 fois

Description

Bonjour,

L'algorithme du crible segmenté semble être le plus rapide pour calculer des nombres premiers, surtout lorsqu'ils dépassent le milliard.

Le code présenté montre qu'on calcule d'abord, avec un algorithme classique, le crible des nombres premiers jusqu'à la racine carrée de N.
Ensuite, on détermine, segment par segment, les plus grands restants.

Voir CodeS-SourceS: Le crible d'Eratosthène classique.

Cette première version (A) s'inspire du code (non optimisé) de Kim Wallisch segmented_sieve.cpp, qui a des performances assez comparables.
typedef int64_t i64;
typedef unsigned int uint;
const uint SS=32768; // SegmentSize
bool *seg=(bool*)malloc(SS),*ptC;

i64 SegmA(i64 N) {
  uint sqrtN=(uint)std::sqrt((double)N);
  i64 s=2,n=3,c=(N<2)?0:1; // c: quantité de premiers 
  ptC=(bool*)malloc(sqrtN+1);
  for(uint i=0; i<=sqrtN; ++i) ptC[i]=true;
  for(uint i=2; i*i<=sqrtN; ++i) // Crible d'Eratosthène classique
    if(ptC[i])
      for(uint q=sqrtN/i; q>=i; --q)
        if(ptC[q]) ptC[i*q]=false;
  std::vector<uint> pos,nxt;
  for(i64 a=0; a<=N; a+=SS) { // Segments
    for (uint i=0; i<SS; ++i) seg[i]=true;
    i64 b=min(a+SS-1,N);
    for(i64 ss=s*s; ss<=b; s++,ss=s*s)
      if(ptC[s]) {pos.push_back((uint)(s+s)); nxt.push_back((uint)(ss-a));}
    for(uint i=1; i<pos.size(); i++) {
      uint j=nxt[i];
      for(uint k=pos[i]; j<SS; j+=k) seg[j]=false;
      nxt[i]=j-SS;
    }
    while (n<=b) {
      if(seg[n-a]) c++; // n est un nombre premier
      n+=2;
    }
  }
  return c;
}

Mon (même) ordinateur donne l'output suivant:
4/10, 0 ms
25/100, 0 ms
168/1000, 0 ms
1229/10000, 0 ms
9592/100000, 0 ms
78498/1000000, 0 ms
664579/10000000, 15 ms
5761455/100000000, 140 ms
50847534/1000000000, 1688 ms
455052511/10000000000, 22016 ms
4118054813/100000000000, 326547 ms

Et également: 203268793/4294709602, 8906 ms

Consultez le fichier Nombres premiers qui vous permet de comparer différents algorithmes.

Bonne lecture ...

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

Bonjour,

Merci pour votre intérêt.

Cet article fait partie d'une série qui essaye de faire connaître quelques algorithmes (bons ou moins bons) sur les Nombres premiers.

Il me semble qu'une bonne manière de comparer l'efficacité d'algorithmes est de mesurer le temps utilisé pour déterminer les nombres premiers jusqu'à N. En fait, on se contente de déterminer le crible correspondant (sans sauver, afficher ou stocker explicitement les nombres premiers correspondants), mais en indiquant où ou comment on peut les récupérer.
De plus, le fait d'afficher la quantité de nombres premiers trouvés permet de bien tester le code.

Chaque article (ou suite d'articles) comporte en général plusieurs codes qui permettent de se persuader des d'améliorations proposés.

Dans un complément prochain du présent article, le crible sera réduit à des "bits", comme dans Atkin-Biz ou Mult.

Et bientôt, il sera également proposé de travailler avec un crible épuré des non-multiples de [2], [2,3], [2,3,5], … comme dans EratoOdd, Cycle additif ou Cycle additif Bis. La méthode du cycle additif est en fait une généralisation de cette idée.

Je vais également approfondir la méthode utilisée par pgl10 dans Mon crible d'Eratosthène, car elle me semble assez différente de celle des Cycles additifs.

Cordialement, WV
Messages postés
329
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
26 juillet 2021
2
Bonjour KX,
Je connais très bien tous les envois de M. William Voirol.
Et je connais bien aussi l'un des avantages de la méthode du crible segmenté : la performance.
Mais, mon envoi référencé n'est pas un concurrent mais un complément du programme présenté ici. En effet, compter le nombre de nombres premiers compris entre 1 et n est un problème classique. Mais utiliser le crible d'Ératosthène pour traiter ensuite et rapidement une série d'interrogations relatives aux nombres entiers premiers et composés est aussi une situation classique voisine et différente, ne serait-ce qu'afficher le nombre de nombres premiers compris entre 1 et tout un ensemble de 1000, ou plus, nombres entiers donnés.
Salut.
Messages postés
16400
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
21 septembre 2021
122
Bonjour pgl10,

William Voirol a déjà publié de nombreux codes, y compris le crible d’Ératosthène dont tu parles (en plusieurs versions), dont il a mis d'ailleurs un lien dans sa description.

Ici il s'agit d'une approche différente, dont le but n'est pas de conserver toutes les valeurs, mais comme indiqué d'être le plus rapide.

Si tu consultes la page de comparatif de ses résultats tu verras entre autres :
Test avec Max = 4'294'709'602 (=> 203'268'793 nombres premiers).
Le crible d'Eratosthène classique : 14.925 s
Nombres premiers: Crible segmenté (A) : 8.906 s
Messages postés
329
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
26 juillet 2021
2
Bonjour M. William Voirol,
Vous savez très bien qu'il n'est pas toujours suffisant de calculer le nombre
de nombres premiers entre 1 et n, il faut assez souvent pouvoir les conserver
tous pour répondre à des questions comme :
combien y a-t-il de nombres premiers entre 1 et x ?
le nombre x est-il premier ?
quel est le rang du nombre x ?
quel est le nombre premier qui suit le nombre x ?
quel est le nombre premier ayant le rang y ?
C'est pourquoi dans le programme de CCM-CodeS-SourceS suivant :
http://codes-sources.commentcamarche.net/source/100217-mon-crible-d-eratosthene
on gagne de la place mémoire pour l'archive du crible en omettant d'y traiter
et d'y représenter les multiples de 2, 3, 5 et 7 d'une part et en se limitant
à un indicateur, premier ou composé, sur 1 bit pour les autres nombres criblés.
Dans cette version on peut cribler les nombres de 1 à 250 000 000 000
avec un crible de 7 142 857 143 octets.
Le 9 920 079 604-ième nombre premier est : 249 999 999 973 !
Le temps d'exécution du calcul n'y est pas particulièrement optimisé,
mais ce programme permet de répondre aux questions énoncées ci-dessus.
On doit probablement pouvoir faire encore mieux, peut-être en y joignant
la méthode du crible segmenté.
Bien cordialement, pgl10

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.