begin process at 2012 05 27 06:04:57
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > CALCUL DES NOMBRES PREMIERS PAR LA CRIBLE D'ÉRATOSTHÈNE

CALCUL DES NOMBRES PREMIERS PAR LA CRIBLE D'ÉRATOSTHÈNE


 Information sur la source

Note :
Aucune note
Catégorie :Maths & Algorithmes Source .NET ( DotNet ) Classé sous :nombre premier, crible ératosthène, ératosthène, nombrespremiers, yield return Niveau :Débutant Date de création :02/12/2007 Date de mise à jour :03/12/2007 15:53:24 Vu :12 666
Auteur : jesusonline

Ecrire un message privé
Site perso
Ce membre participe au partage de revenus publicitaires
Commentaire sur cette source (11)
Ajouter un commentaire et/ou une note

 Description

La crible d'ératosthène permet de trouver les n premiers nombres premiers en parcourant de 2 à n tous les nombres et en supprimant les multiples. Pour en savoir plus :

http://en.wikipedia.org/wiki/Sieve_of_Eratosthen es

La méthode Prime utilise le mot clé yield return.
La méthode Prime2 utilise une stack.
La méthode Prime3 est une optimisation algorithmique.
La méthode Prime4 est Prime5 sont des optimisations algorithmique mais ne sont pas toujours plus rapide ... voir commentaires.

Prime2 est plus rapide mais plus gourmand en mémoire à cause de l'utilisation d'une stack, attention puisqu'on utilise une Stack la méthode nous renvoie les nombres à l'envers.

Source

  • static IEnumerable<int> Prime(int max)
  • {
  • BitArray b = new BitArray(max);
  • b.SetAll(true);
  • b[0] = false;
  • b[1] = false;
  • for (int i = 2; i < max; i++)
  • {
  • if (b[i] == true)
  • {
  • yield return i;
  • for (int j = 2 * i; j < max; j += i)
  • {
  • b[j] = false;
  • }
  • }
  • }
  • }
  • static IEnumerable<int> Prime2(int max)
  • {
  • BitArray b = new BitArray(max);
  • b.SetAll(true);
  • b[0] = false;
  • b[1] = false;
  • Stack<int> primes = new Stack<int>();
  • for (int i = 2; i < max; i++)
  • {
  • if (b[i] == true)
  • {
  • primes.Push(i);
  • for (int j = 2 * i; j < max; j += i)
  • {
  • b[j] = false;
  • }
  • }
  • }
  • return primes;
  • }
  • static IEnumerable<int> Prime3(int max)
  • {
  • BitArray b = new BitArray(max);
  • b.SetAll(true);
  • b[0] = false;
  • b[1] = false;
  • Stack<int> primes = new Stack<int>();
  • for (int i = 2; i < max; i++)
  • {
  • if (b[i] == true)
  • {
  • primes.Push(i);
  • // nécessaire si i > Math.Sqrt(int.MaxValue);
  • long j = (long)i * i;
  • if (j < max)
  • {
  • for (int k = (int)j; k < max; k += i)
  • {
  • b[k] = false;
  • }
  • }
  • }
  • }
  • return primes;
  • }
  • static IEnumerable<int> Prime4(int max)
  • {
  • BitArray b = new BitArray(max);
  • b.SetAll(true);
  • b[0] = false;
  • b[1] = false;
  • Stack<int> primes = new Stack<int>();
  • Boolean stopFor = false;
  • for (int i = 2; i < max; i++)
  • {
  • if (b[i] == true)
  • {
  • primes.Push(i);
  • if (!stopFor)
  • {
  • // nécessaire si i > Math.Sqrt(int.MaxValue);
  • long j = (long)i * i;
  • if (j < max)
  • {
  • for (int k = (int)j; k < max; k += i)
  • {
  • b[k] = false;
  • }
  • }
  • else
  • {
  • stopFor = true;
  • }
  • }
  • }
  • }
  • return primes;
  • }
  • static IEnumerable<int> Prime5(int max)
  • {
  • BitArray b = new BitArray(max);
  • b.SetAll(true);
  • b[0] = false;
  • b[1] = false;
  • Stack<int> primes = new Stack<int>();
  • int pivot = (int)Math.Truncate(Math.Sqrt(max)) + 1;
  • for (int i = 2; i < pivot; i++)
  • {
  • if (b[i] == true)
  • {
  • primes.Push(i);
  • // nécessaire si i > Math.Sqrt(int.MaxValue);
  • long j = (long)i * i;
  • if (j < max)
  • {
  • for (int k = (int)j; k < max; k += i)
  • {
  • b[k] = false;
  • }
  • }
  • }
  • }
  • for (int i = pivot; i < max; i++)
  • {
  • if (b[i] == true)
  • {
  • primes.Push(i);
  • }
  • }
  • return primes;
  • } 
        static IEnumerable<int> Prime(int max)
        {
            BitArray b = new BitArray(max);
            b.SetAll(true);

            b[0] = false;
            b[1] = false;

            for (int i = 2; i < max; i++)
            {
                if (b[i] == true)
                {
                    yield return i;
                    for (int j = 2 * i; j < max; j += i)
                    {
                        b[j] = false;
                    }
                }
            }
        }

        static IEnumerable<int> Prime2(int max)
        {
            BitArray b = new BitArray(max);
            b.SetAll(true);

            b[0] = false;
            b[1] = false;

            Stack<int> primes = new Stack<int>();

            for (int i = 2; i < max; i++)
            {
                if (b[i] == true)
                {
                    primes.Push(i);
                    for (int j = 2 * i; j < max; j += i)
                    {
                        b[j] = false;
                    }
                }
            }

            return primes;
        }

        static IEnumerable<int> Prime3(int max)
        {
            BitArray b = new BitArray(max);
            b.SetAll(true);
            b[0] = false;
            b[1] = false;
            Stack<int> primes = new Stack<int>();

            for (int i = 2; i < max; i++)
            {
                if (b[i] == true)
                {
                    primes.Push(i);
                    // nécessaire si i > Math.Sqrt(int.MaxValue); 
                    long j = (long)i * i;
                    if (j < max)
                    {
                        for (int k = (int)j; k < max; k += i)
                        {
                            b[k] = false;
                        }
                    }
                }
            }
            return primes;
        }

        static IEnumerable<int> Prime4(int max)
        {
            BitArray b = new BitArray(max);
            b.SetAll(true);
            b[0] = false;
            b[1] = false;
            Stack<int> primes = new Stack<int>();

            Boolean stopFor = false;
            for (int i = 2; i < max; i++)
            {
                if (b[i] == true)
                {
                    primes.Push(i);

                    if (!stopFor)
                    {
                        // nécessaire si i > Math.Sqrt(int.MaxValue); 
                        long j = (long)i * i;
                        if (j < max)
                        {
                            for (int k = (int)j; k < max; k += i)
                            {
                                b[k] = false;
                            }
                        }
                        else
                        {
                            stopFor = true;
                        }
                    }
                }
            }
            return primes;
        }

        static IEnumerable<int> Prime5(int max)
        {
            BitArray b = new BitArray(max);
            b.SetAll(true);
            b[0] = false;
            b[1] = false;
            Stack<int> primes = new Stack<int>();

            int pivot = (int)Math.Truncate(Math.Sqrt(max)) + 1;

            for (int i = 2; i < pivot; i++)
            {
                if (b[i] == true)
                {
                    primes.Push(i);

                    // nécessaire si i > Math.Sqrt(int.MaxValue); 
                    long j = (long)i * i;
                    if (j < max)
                    {
                        for (int k = (int)j; k < max; k += i)
                        {
                            b[k] = false;
                        }
                    }
                }
            }

            for (int i = pivot; i < max; i++)
            {
                if (b[i] == true)
                {
                    primes.Push(i);
                }
            }

            return primes;
        }



 Historique

02 décembre 2007 16:24:15 :
Erreur de copier/coller
02 décembre 2007 17:00:07 :
Optimisation en utilisant une stack plutot qu'un yield return
02 décembre 2007 18:05:40 :
Optimisation algorithmique
03 décembre 2007 12:42:58 :
Optimisation algo proposé par billou_13
03 décembre 2007 15:53:25 :
Rajout de Prime5

 Sources du même auteur

Source .NET (Dotnet) ENTITY FRAMEWORK - AVOIR UN INCLUDE TYPÉ
Source .NET (Dotnet) WEBTESTPLUGIN - IGNORER DES URLS LORS D'UN TEST WEB VISUAL S...
Source avec Zip Source .NET (Dotnet) MECANISME DE SYNCHRONISATION DE THREAD - MONITOR, MUTEX, SEM...
Source avec Zip Source avec une capture Source .NET (Dotnet) GESTION DES IMPRIMANTES - ADDIN POUR WHS
Source .NET (Dotnet) MARQUER UN DOCUMENT OPENXML EN TANT QUE FINAL
Toutes les sources de jesusonline

 Sources de la même categorie

Source .NET (Dotnet) COMBINAISONS DE CARACTÈRES par whismeril
Source avec Zip Source avec une capture (CONSOLE) TROUVER LA CLEF D'UN CODE INSEE EN DONNANT SES 13 ... par Maxime95k
Source avec Zip Source .NET (Dotnet) QUANTUM BIBLIOTHÈQUE MATHÉMATIQUES par QuantumNet
Source avec Zip Source avec une capture Source .NET (Dotnet) ALGORITHME DE LA PROPENSION par olivieram2
Source avec Zip Source .NET (Dotnet) PETITE LIBRAIRIE MATHÉMATIQUE par dodo7263
Toutes les sources de la catégorie Maths & Algorithmes

Commentaires et avis

Commentaire de billou_13 le 03/12/2007 09:17:34

Bonjour à toi,

Très intéressant comme source. Cependant, je ne vois pas trop pourquoi tu n'as pas implémenté la condition suivante (que je viens de lire ^^).
Citation: http://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne
Étape 4. Si le carré du nombre suivant non rayé est inférieur à 20, alors on recommence à l'étape 2 sinon on déclare tous les entiers restants non rayés premiers.

Il y a un début sur le prime 3. C'est peut-être alors pour des raisons de performance ?

Bonne journée,

PS: à quand la source sur le Crible d'Atkin ^^

Commentaire de Malkuth le 03/12/2007 09:54:18

Pourquoi ne pas utiliser une queue<T> au lieu d'une stack<T>?
plus lent?

Commentaire de jesusonline le 03/12/2007 11:04:33 administrateur CS

@Malkuth : J'ai testé les 2, Stack<T> est plus rapide que Queue<T>

@Billou_13 : Prime3 a cet optimisation - je l'ai fait dans un second temps pour simplifier l'algo.
Je vais essayer d'implémenter Atkin mais je promet rien ;-)

Commentaire de billou_13 le 03/12/2007 12:22:58

C'est exact mais je pense que tu peux optimiser un petit peu plus car le test est réalisé pour tous les entiers de sqrt(max) jusqu'à max.
Hors, lorsque un entier au carré > max , son prochain aussi.
Alors, tu peux essayer de mettre un booléen pour éviter de faire la multiplication pour tous les autres.  Cela te fera peut-être gagner du temps ? à tester ^^.

J'ai vu aussi sur le net que beaucoup de code (en c) notamment, mettent en place cette vérification au niveau de la boucle. Ce qui te donnerai
for (int i = 2; i < Math.Sqrt(int.MaxValue); i++)
{
...
}
Mais je pense que tu n'as pas fait cela car tu veux empiler toutes les réponses dans la pile.

Ps: pour information, le prochain nombre premier trouvé comptant plus de 10 millions de chiffres offrira 100.000$ à son propriétaire ^^
On se demande bien ce qui peut motiver à payer un nombre aussi cher ? (peut-être pour sortir un bouquin le contenant ...)

Commentaire de jesusonline le 03/12/2007 12:44:34 administrateur CS

Bien vu :p
J'ai rajouté une méthode Prime4. Par contre j'ai eu des effets bizarre, apparement sur les petits nombres < 1000, Prime4 est plus lent que Prime3 ... :-/

Commentaire de Malkuth le 03/12/2007 15:17:17

Re ;)
je m'en doutais pour le queue mais n'ayant pas testé...

pour accéléré le prime4 pourquoi ne pas faire 2 boucle :
ex :

int maxbcl1 = ((int)Math.Sqrt(int.MaxValue))) + 1

for (int i = 2; i < maxbcl1; i++)
   if (b[i] == true)
   {
      primes.Push(i);
      for (int k = (int)i*i; k < max; k += i)
         b[k] = false;                
   }

for (int i = maxbcl1; i < max; i++)
   if (b[i] == true)
      primes.Push(i);

return primes;


Ca devrait faire pas mal de test en moins à voir aussi si les boucles for sont les plus rapide pour cette algo.

Commentaire de Malkuth le 03/12/2007 15:20:16

billou_13 > à vérifié mais il me semble que de mettre le Math.Sqrt(...) dans la condition de boucle, force le recalcul a chaque itération (reflector devrais nous en dire plus).

Commentaire de jesusonline le 03/12/2007 15:55:22 administrateur CS

Malkuth : je viens de rajouter Prime5 à partir de ce que tu proposes.

Pour tester les perfs, j'utilise ce code :

static void Main(string[] args)
{

    foreach (var max in new int[] { 1000, 100000, 500000, 1000000, 2000000, 5000000, 10000000 })
    {
        long time1 = 0;
        long time2 = 0;
        for (int i = 0; i < 5; i++)
        {
            Stopwatch sw = Stopwatch.StartNew();
            var n = Prime4(max);
            sw.Stop();
            time1 += sw.ElapsedMilliseconds;

            sw = Stopwatch.StartNew();
            n = Prime5(max);
            sw.Stop();
            time2 += sw.ElapsedMilliseconds;
        }

        if (time1 > time2)
            Console.ForegroundColor = ConsoleColor.Green;
        else
            Console.ForegroundColor = ConsoleColor.Red;

        Console.WriteLine("Pour les nombres premiers inférieurs à {0:N0} : {1:N0}\t{2:N0}", max, time1, time2);

        Console.ForegroundColor = ConsoleColor.Gray;

    }
}

Prime3, Prime4, Prime5 sont assez équivalent niveau perf, il faut que je fasse plus de test pour comprendre qui est plus rapide dans tel cas et surtout pourquoi.

Commentaire de Malkuth le 03/12/2007 16:48:34

if (j < max)
{
....
}

Cette condition n'est plus néscessaire car i*i est toujours inférieur a max dans la premiére boucle.

Commentaire de billou_13 le 03/12/2007 17:40:54

@MALKUTH: Je me suis poser la même question concernant le sqrt dans la boucle for. Mais comme je ne suis pas comme saint thomas ^^, j'ai pas testé.
Cependant, ayant vu que cette boucle étaient souvent constaté sur le net (calcul dans la condition d'un for), je me dis que cela doit surement être optimiser derrière. Si tu as la réponse à cette question, cela m'intéresse beaucoup !

Bonne soirée à vous,

Remarque: Tout ces soucis d'optimisation ceci me font penser au jour ou j'ai découvert que ma fonction de tri par ordre alphabétique d'un tableau était super couteuse car je bouclais n² de fois dans le tableau (je sais, c'est pas beau). Beaucoup de méthodes sont plus sympathiques, pour les curieux: http://interstices.info/display.jsp?id=c_6973

Commentaire de Malkuth le 03/12/2007 19:01:06

héhé ^^
Trouvé une solution jusqu'a plus de 2 fois plus rapide... je vous laisse mariné mais il est question de unsafe.

billou_13 >

Effectivement on trouve souvent se genre de contruction avec des calcule dans la condition mais je me demande si se n'est pas de la "parresse" à ne pas vouloir se tapé une variable locale intermédaire.
En tout cas, toute personne qui utilise cette construction sans avoir vérifié précédement ce qui sortai comme code aprés compilation commetrait une grosse erreur :
imagine que la condition de limite supérieur prenne une demi-seconde de calcule à elle seule et qu'on la repette 500 fois où plus alors que rien n'en modifie le résultat...
Par contre si le résultat de cette fonction peut-être modifié dans le temps,
il faut bien évidément metre le calcul dans la condition, on essais toutefois de réduire ces calcul au max en précalculant les résultats intermediaire.

Enfin même sans reflector, il est facile de vérifie le comportement de la boucle for :
for (; MessageBox.Show("", "", MessageBoxButtons.OKCancel) == DialogResult.Cancel; ) ;

 Ajouter un commentaire

Nos sponsors


Sondage...

CalendriCode

Mai 2012
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

Consulter la suite du CalendriCode

A découvrir
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 1,794 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)