Nombres premiers: Crible d'Atkin
William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
-
20 sept. 2013 à 11:24
shadow1779 Messages postés 706 Date d'inscription mercredi 17 novembre 2004 Statut Membre Dernière intervention 29 septembre 2013 - 29 sept. 2013 à 11:37
shadow1779 Messages postés 706 Date d'inscription mercredi 17 novembre 2004 Statut Membre Dernière intervention 29 septembre 2013 - 29 sept. 2013 à 11:37
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/100128-nombres-premiers-crible-d-atkin
https://codes-sources.commentcamarche.net/source/100128-nombres-premiers-crible-d-atkin
29 sept. 2013 à 11:37
Quoi qu'il en soit source sympa, un bon truc de matheux presque incompréhensible quand on maitrise pas le sujet xD mais néanmoins chapeau pour le portage en js (meme si je ne comprend toujours pas l'interet de l'usage du cryble d'Atkin dans la vie de tous les jours)
22 sept. 2013 à 15:39
C'est très intéressant de publier plusieurs solutions pour le même problème.
Ici on calcule en Javascript un indicateur pour chaque nombre entre 1 et nmax (exemple : nmax = 100 000 000) selon qu'il est premier ou non. Ceci est un problème différent du calcul du nombre premier immédiatement inférieur (ou supérieur) à un nombre donné. Et c'est aussi, bien sûr, différent du calcul pour savoir si un nombre donné est premier ou non. J'ai traité en C++ le même problème que celui traité ici.
A : http://codes-sources.commentcamarche.net/source/53321-crible-d-eratosthene-optimise on peut voir qu'il est assez facile de marquer les 203268793 nombres premiers entre 1 et 4294709602 (4 294 709 602).
De plus, avec la variante qui y est référencée et qui utilise les entiers int64 en mode x64 on peut aller beaucoup plus loin et, par exemple, marquer les 4 118 054 813 nombres entiers entre 1 et 100 000 000 000 en quelques dizaines de minutes.
D'où mes questions : 1°) est-ce que Javascript peut calculer aussi bien et aussi vite que C++ avec de grands entiers ou bien a-t-il une limitation plus contraignante que C++ ? Et si oui laquelle ? 2°) Est-ce que le crible d'Atkin est plus rapide que la crible d'Ératosthène ?
Merci, pgl10