Nombres premiers: crible des multiplications
William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
-
18 oct. 2013 à 10:01
William VOIROL Messages postés 261 Date d'inscription mardi 12 décembre 2006 Statut Membre Dernière intervention 10 juin 2019 - 12 févr. 2014 à 09:49
William VOIROL Messages postés 261 Date d'inscription mardi 12 décembre 2006 Statut Membre Dernière intervention 10 juin 2019 - 12 févr. 2014 à 09:49
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/100175-nombres-premiers-crible-des-multiplications
https://codes-sources.commentcamarche.net/source/100175-nombres-premiers-crible-des-multiplications
12 févr. 2014 à 09:49
Je vous remercie pour l'intérêt que vous montrez pour cet article et vous prie de m'excuser pour le retard de ma réponse.
La fonction proposée permet de savoir si un nombre donné est premier ou non.
Je n'ai pas encore abordé ce domaine, qui inclut aussi la décomposition d'un nombre en facteurs.
J'espère pouvoir le faire d'ici quelques mois.
8 janv. 2014 à 12:23
(function(){function isPrime(){ var n=this;On utilise les propriétés (n et 2,3,5,7...) de la fonction isPrime pour pouvoir réutiiser les calculs précédement effectuésif(isPrime[n]){ return true; }
if( n<11|| ! ((n%2)&&(n%3)&&(n%7)&&(n%9)) ){ return false; }
for (var i=5, l=Math.sqrt(n)+1; i<l; i+=6){
if( !(n%i) || !(n%(i+2)) ){ return false; }
}
return isPrime.n++ < 1e6 ? (isPrime[n]=true) : true;
};
var p=isPrime;p.n=0;p[2]=p[3]=p[5]=p[7]=true;
Number.prototype.isPrime=p;
}());
// Usage
alert(Number(10001).isPrime())
Modifié par William VOIROL le 19/10/2013 à 10:31
Entre-temps, j'ai terminé une "optimisation en C" de l'algorithme (voir ***).
Voici quelques mesures du temps d'exécution pour déterminer le crible (d'Eratosthène) avec une valeur maximale mx <= 4'294'709'602 (correspondant à 203'268'793 nombres premiers).
(année, temps d'exéc., mémoire, lien):
2003, 53.461 s, bit[Max/2], 1 000 000 de nombres premiers en 0.062 secondes
2011, 63.773 s, bit[Max/2], crible d'eratosthène optimisé
2013, 23.167 s, bit[Max/2], Nombres premiers: crible d'Eratosthène
2013, 17.659 s, bit[Max/3], Crible des multiplications ***
Merci d'avance à tous ceux qui me proposent d'améliorer, compléter ou corriger cette liste.
Examinez aussi "quelques codes" sur les nombres premiers.
18 oct. 2013 à 10:14
Merci