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

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (jesusonline)