Calcul des nombres premiers par la crible d'ératosthène

Commenter

Contenu du snippet

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_Eratosthenes

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 / Exemple : 


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;
        }

A voir également

Du même auteur (jesusonline)