OBTENIR TOUTES LES NOMBRES PREMIERS DANS UNE GRANDE RANGÉE AU MOINS DE 10 MS!

Signaler
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
-
Messages postés
77
Date d'inscription
mardi 27 juin 2006
Statut
Membre
Dernière intervention
12 août 2010
-
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/42350-obtenir-toutes-les-nombres-premiers-dans-une-grande-rangee-au-moins-de-10-ms

Messages postés
77
Date d'inscription
mardi 27 juin 2006
Statut
Membre
Dernière intervention
12 août 2010

http://www.cppfrance.com/codes/RECHERCHE-NOMBRES-PREMIERS-CRIBLE-ERATOSTHENE_38335.aspx

Voila un exemple d'optimisation avec la mémoire. En plus avec les opérateurs basiques (&, |, <<, >>) on gagne beaucoup en vitesse.
Messages postés
77
Date d'inscription
mardi 27 juin 2006
Statut
Membre
Dernière intervention
12 août 2010

Pour bcc55, ça ne compile pas...
Messages postés
77
Date d'inscription
mardi 27 juin 2006
Statut
Membre
Dernière intervention
12 août 2010

"exactement Kirva!
son seul inconvénient c'est la grande mémoire!dieu merci qu'on est dans l'époque des 1Go de RAM!
a bientot.."
Justement pour la mémoire il y a une optimisation : on peut juste utiliser un bit par nombre impair, ça diminue par 16 l'espace mémoire requis. Comme ça on gagne 8 ans sur la technologie (loi de Moore). Pour la rapidité je ne sais pas si ça rend plus rapide ou moins (je dirais moins mais on ne sais pas car les opérateurs << et >> sont extremement rapides).
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

Ben si, et c'est même très facile à prouver (ce qui ajoute à l'élégance de la démonstration ^^). Mais on parle ici de trouver tous les nombres premiers dans un intervalle fini, et ça, il y en a un nombre fini.
Afficher les 25 commentaires