Nombres premiers: Crible segmenté (A)

Signaler
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
-
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/101541-nombres-premiers-crible-segmente-a

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
16372
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
23 juillet 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