Le crible d'Eratosthène classique
William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
-
19 mars 2014 à 07:46
William VOIROL Messages postés 261 Date d'inscription mardi 12 décembre 2006 Statut Membre Dernière intervention 10 juin 2019 - 30 mars 2014 à 08:05
William VOIROL Messages postés 261 Date d'inscription mardi 12 décembre 2006 Statut Membre Dernière intervention 10 juin 2019 - 30 mars 2014 à 08:05
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/100460-le-crible-d-eratosthene-classique
https://codes-sources.commentcamarche.net/source/100460-le-crible-d-eratosthene-classique
- Quel est le système le plus classique de numérotation des versions ?
- Programmation du calcul d'une obligation classique
- Classique code : conversion decimale=>binaire
- Une date Hébreu -> Date Grégorien (soit le calendrier classique)
- Affichage sur l'ecran sans interruption du programme ( msgbox) classique) en vbs
30 mars 2014 à 08:05
Résumé de mes articles sur les nombres premiers vous montre que pour le moment, je n'ai pas réussi à le confirmer.
Je vous serai très reconnaissant si vous pouviez me donner quelques précisions.
29 mars 2014 à 07:21
Merci beaucoup pour votre simplification du calcul de la valeur initiale j=(mx/p-1)/2.
Mon raisonnement était encore basé sur JavaScript, qui ne connait pas la division entière.
Si vous le permettez, je l'introduirai prochainement.
29 mars 2014 à 07:20
L'article Le crible d'Ératosthène que vous avez eu l'amabilité de me communiquer montre clairement que l'idée était déjà connue.
Je vais donc prochainement "adapter" mon article.
Malgré cela, j'ai eu beaucoup de plaisir à "réinventer la roue" !
29 mars 2014 à 07:17
Merci pour vos conseils.
Il est très intéressant d'utiliser un octet pour stocker les 8 candidats possibles par segment de 30 nombres.
Dans Nombres premiers: Crible avec cycle additif , le chapitre Cycle235 ouvre également cette possibilité (len=8, gap=30).
Et pour les cycles plus grands, len est toujours un multiple de 8 !
Quant au codage de Huffman, il pourrait également être intéressant pour "stocker" les grands cycles.
19 mars 2014 à 17:25
Cette amélioration progressive des performances est bien intéressante.
Je crois que l'on peut encore simplifier en :
bool *EratoOdd(uint mx) { bool *isPrime=(bool*)malloc((mx+1)/2); memset(isPrime,true,(mx+1)/2); for (uint i=1,p=3; p*p<=mx; ++i,p+=2) if (isPrime[i]) { for (uint j=(mx/p-1)/2; j>=i; --j) if (isPrime[j]) isPrime[i+p*j]=false; } return isPrime; }Mais les performances restent inchangées.
19 mars 2014 à 16:04
Après, si tu veux être encore plus rapide, il y a le crible d'Atkin, qui est plus dur à coder, mais considérablement plus puissant.
Un autre problème intéressant est le test de primalité individuel (Une fonction qui prend un nombre et dit s'il est premier sans calculer tous les autres nombres premiers).L'algorithme AKS permet de coder cette fonction en temps polynomial : www.trigofacile.com/maths/curiosite/primarite/aks/pdf/algorithme-aks.pdf
19 mars 2014 à 13:54
Voici 3 conseils:
-Avec un octet, tu peux stocker les nombres premiers entre n et n+29 : seuls les nombres congrus à 1,7,11,13,17,19,23 et 29 modulo 30 peuvent être premiers.
-Si tu cherches à stocker tout ça dans une base de données, tu peux utiliser le codage de Huffman, qui économisera une bonne quantité de mémoire (car sur 30 nombres consécutifs, il est rare que plus de 2 soient premiers, sauf sur de petits entiers, et certains octets reviendront donc plus souvent).
-Enfin, si jamais tu passe la limite des unsigned long, tu peux utiliser des bignums (gmplib.org).