GÉNÉRATION DE NOMBRES PREMIERS ET STOCKAGE DANS UN FICHIER
LeFauve42
Messages postés
239
Date d'inscription
vendredi 20 octobre 2006
Statut
Membre
Dernière intervention
20 avril 2009
-
23 avril 2007 à 09:36
LeFauve42 Messages postés 239 Date d'inscription vendredi 20 octobre 2006 Statut Membre Dernière intervention 20 avril 2009 - 23 avril 2007 à 09:36
LeFauve42 Messages postés 239 Date d'inscription vendredi 20 octobre 2006 Statut Membre Dernière intervention 20 avril 2009 - 23 avril 2007 à 09:36
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/42378-generation-de-nombres-premiers-et-stockage-dans-un-fichier
https://codes-sources.commentcamarche.net/source/42378-generation-de-nombres-premiers-et-stockage-dans-un-fichier
23 avril 2007 à 09:36
C'est tres joli et bien ecrit, mais l'algorithme est tres basique, et loin d'etre le plus performant.
Vous devriez regarder du cote du cribble d'Erastothene (il y a un exemple ici: http://www.cppfrance.com/code.aspx?ID=10645 (mais je ne l'ai pas regarde en details. Inspirez vous surtout de l'algo)).
Le principal defaut du cribble est que si vous voulez le nieme nombre premier, vous devez d'abord calculer les n-1 precedents, mais vu que votre programme genere une liste, ca ne devrait pas poser de problemes.
Deux petits conseils d'optimisation:
- Les nombres pairs ne sont jamais premiers (a part 2), donc vous pouvez utiliser un tableau deux fois plus petit (il suffit d'ajouter a la main 1 et 2 au debut de votre liste, puis si le cribble trouve le chiffre c comme premier, vous ajoutez a votre liste (2*c)+1 et de cribbler le tableau tous les (2*c+1)).
- Les 3-4 premieres iterations du tableau prennent pratiquement plus de temps que les millions suivantes. Apres les avoir realisees, si vous regardez le contenu du tableau, vous remarquerez que son contenu se repete tous les 20-30 caracteres (si vous stockez un bit pour chaque element). Il est donc tres efficace de preremplir ce tableau avec en dur le motif qui se repete, puis de d'emarer les iterations.
Bonne chance avec les nombres premiers :o)
Eric