GÉNÉRATION DE NOMBRES PREMIERS ET STOCKAGE DANS UN FICHIER
LeFauve42
Messages postés239Date d'inscriptionvendredi 20 octobre 2006StatutMembreDernière intervention20 avril 2009
-
23 avril 2007 à 09:36
LeFauve42
Messages postés239Date d'inscriptionvendredi 20 octobre 2006StatutMembreDernière intervention20 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.
LeFauve42
Messages postés239Date d'inscriptionvendredi 20 octobre 2006StatutMembreDernière intervention20 avril 2009 23 avril 2007 à 09:36
Bonjour,
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.
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