CALCUL DES NOMBRES PREMIERS PAR LA CRIBLE D'ÉRATOSTHÈNE nombre premier, crible ératosthène, ératosthène, nombrespremiers, yield return, Source N°44893

Information sur la source

Catégorie :Maths & Algorithmes

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 : 3 250

Auteur : jesusonline

Site perso

Ecrire un message privé

Ce membre participe au partage de revenus publicitaires

Note :
Aucune note

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_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

Version Visual Basic de ce code disponible !

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

Toutes les sources de jesusonline

Sources de la même categorie

Toutes les sources de la catégorie Maths & Algorithmes

Commentaires

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