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

Soyez le premier à donner votre avis sur cette source.

Snippet vu 16 557 fois - Téléchargée 18 fois

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

Ajouter un commentaire

Commentaires

cs_Malkuth
Messages postés
268
Date d'inscription
samedi 22 février 2003
Statut
Membre
Dernière intervention
24 avril 2013
2
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; ) ;
billou_13
Messages postés
860
Date d'inscription
jeudi 4 mars 2004
Statut
Membre
Dernière intervention
19 août 2014
17
@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
cs_Malkuth
Messages postés
268
Date d'inscription
samedi 22 février 2003
Statut
Membre
Dernière intervention
24 avril 2013
2
if (j < max)
{
....
}

Cette condition n'est plus néscessaire car i*i est toujours inférieur a max dans la premiére boucle.
jesusonline
Messages postés
6814
Date d'inscription
dimanche 15 décembre 2002
Statut
Modérateur
Dernière intervention
13 octobre 2010
18
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.
cs_Malkuth
Messages postés
268
Date d'inscription
samedi 22 février 2003
Statut
Membre
Dernière intervention
24 avril 2013
2
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).

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.