Bonjour,
Je dois trouver les nombres premiers de 1 à 100 en C.
Pour ça, j'ai écris les nombres dans un tableau via ce code :

C'est après que se pose mon problème. Je ne vois pas comment retirer les multiples des nombres premiers.
Si quelqu'un à une idée, merci de bien vouloir m'aider.

Bah plutot que retirer, tu ajoutes seulement si le nombre est bien premier. Donc tu testes avant.

indice :
Pour tester si un nombre premier, tu testes juste avec les nombres premiers plus petits ou égaux à racinecarree(nb)
=> ça évite énormément de tests inutiles : genre 51 ne peut pas être un multiple de 50, au maximum tu trouveras des multiples jusqu'à n à n² = 51
=> et pas la peine non plus de tester si le nombre est un multiple d'un nombre qui n'est pas premier
 
y'a d'autres approche bien plus rapides, mais bon, celle-ci est évidente et simple à mettre en place.
 
 
edition : nombre "premiers" je veux dire, pas "entiers"

au passage:
http://fr.wikipedia.org/wiki/Cribl [...] th%C3%A8ne

Faudrait faire des calculs que je sais pas faire, mais j'aimerais bien comparer avec ma méthode. Je ne suis pas sûr que le truc que tu indique soit réellement mieux
 
Quoique pour les grandes valeurs, effectivement ta solution semmble meilleure (mais plus consommatrice en mémoire... j'imagine si on doit rechercher les nombres entiers de 0 à 2^64, ça fait un sacré array à mettre en mémoire, même si c'est un simple array de bit qui est retenu (optimisation à la con qui rend le code imbittable )

merci de vos réponses, je vais voir ce que jpeux faire.

C'est un point de vue algorithmique, pas optimisation (donc mieux ou pas, c'est juste une source de doc en plus).
 
Cela dit, dans la discussion, on trouve une implé en perl:
http://fr.wikipedia.org/wiki/Discu [...] th%C3%A8ne

Nan pis en fait j'avais pas lu le titre du topic. C'est effectivement une implantation de cet algo qu'il veut, j'ai répondu à côté de la plaque

ah bah ok lol alors hein

http://www.troubleshooters.com/cod [...] umbers.htm

Sinon, pour en revenir à cet algo donc...
 
array de byte avec comme valeurs 0 ou 1 (et indices 2..n, je te laisse t'amuser avec un offset pour partir de 0 )
 
ensuite, tu les initialise tous à 0, et quand ils sont cochés, tu passes à 1
 
Pour le reste, tu suis bêtement les explications du lien de darkalt3. Ensuite t'as plus qu'à lire les valeurs dans ton tableau, et n'afficher que les indices de ceux qui sont encore à 0

C'est marrant, je ne reconnais pas ma technique dans les tests du gars. Pourtant elle est mieux par exemple que sa première tentative...

LOL.
 
Bon, ben moi je suis nul en analyse de code...
Je pensais pas solution plus rapide pour de petites valeurs et moins rapide pour des grandes...
 
Mais c'est l'inverse
 
Bench sur 2 à 100 :

 
Bench sur 2 à 1000000 :

 
Le code (en C#) :

using System;
using System.Collections.Generic;
using System.Text;
 
namespace nprems
{
    class Program
    {
        static void Main(string[] args)
        {
            int val;
 
            Console.WriteLine("Jusqu'à quelle valeur rechercher des nombres premiers ?" );
            while (!int.TryParse(Console.ReadLine(), out val))
            {
                Console.WriteLine("Nombre invalide. Recommencez..." );
            }
            Console.WriteLine("Liste des nombres premiers jusqu'à {0} :", val);
 
            Console.WriteLine("Da magic solution..." );
            {
                DateTime d1 = DateTime.Now;
                List<int> prems = new List<int>();
                // On sait que 2 est un nombre premier
                prems.Add(2);
 
                // On sait aussi que seuls les nombres impaires au dessus de 2 peuvent être premiers
                for (int i = 3; i <= val; i += 2)
                {
                    int maxi = (int)Math.Sqrt((double)i);
                    bool gotcha = true;
 
                    // On pacours les nombres premiers déjà existants
                    for (int j = 0, max = prems.Count; j < max; j++)
                    {
                        // Pas besoin de tester les nombres premiers supérieurs à sqrt(i)
                        if (prems[j] <= maxi)
                        {
                            if (i % prems[j] == 0)
                            {
                                // Ce n'est pas un nombre premier
                                gotcha = false;
                                break;
                            }
                        }
                    }
                    if (gotcha)
                    {
                        prems.Add(i);
                    }
                }
 
                foreach (int i in prems)
                {
                    Console.WriteLine(i);
                }
 
                Console.WriteLine("Temps d'exécution : {0} ms", DateTime.Now.Subtract(d1).TotalMilliseconds);
            }
 
            Console.WriteLine("Da pas magic solution..." );
            {
                DateTime d1 = DateTime.Now;
                bool[] nbrs = new bool[val + 1];
                int maxi = val + 1;
                for (int i = 2; i < maxi; i++)
                {
                    nbrs[i] = true;
                }
 
                for (int i = 2; i < maxi; i++)
                {
                    if (nbrs[i])
                    {
                        for (int j = i * 2; j < maxi; j++)
                        {
                            if (nbrs[j])
                            {
                                if (j % i == 0)
                                {
                                    nbrs[j] = false;
                                }
                            }
                        }
                    }
                }
 
                for (int i = 2; i < maxi; i++)
                {
                    if (nbrs[i])
                    {
                        Console.WriteLine(i);
                    }
                }
                                
                Console.WriteLine("Temps d'exécution : {0} ms", DateTime.Now.Subtract(d1).TotalMilliseconds);
            }
 
            Console.ReadKey(true);
        }
    }
}

 
Ceci dit, le problème avec les petites valeurs, c'est je pense la lourdeur de l'objet List<>... Avec un int[] initialisé avec une taille arbitraire ce serait je pense plus rapide aussi dans le cas des toutes petites valeurs
 
Evidement, les deux bouts de code retournent le même résultat hein

Avec une prévérence tout de même pour mon code : j'ai un objet List<int> qui ne contient QUE les nombres premiers à la sortie. Alors qu'avec l'algo d'Eratosthènemachin, je me retrouve avec un array de bool que je dois parcourir à chaque fois pour retrouver les indices désirés...
 
En tout cas, je suis content. L'algo que j'ai mis au point en BASIC sur mon C64 (j'avais quoi... 9 ou 10 ans à l'époque ) reste meilleur que ce qu'on étudie à la fac

MagicBuzz, ça t'embêterait de faire du C sur ce forum C ?

Mais tu nous pourris quoi avec ton C# ? On le sait déjà que tu ne connais pas le C

Mon code Haskell défonce ton code C#
(et en plus il est lisible, et la logique applicative tient en 9 lignes)
(et c'est sans optimisations )

Mon code est parfaitement lisible
 
Sinon, moi les instructions utiles au code (our le premier par exemple) y'a que 11 lignes, en comptant les déclarations... Alors tes 9 lignes...

1/ je fais du C, j'ai juste rajouté un # derrière  
2/ en ce qui concerne l'algo, perso, je vois pas de diff avec le C... pour le premier algo, la seule code qui ne se transpose pas nativement en C, c'est le coup du List<int> et j'ai indiqué qu'un simple array de taille arbitraire à la place fait aussi bien l'affaire... quant au second... mise à part la déclaration d'un array qui n'est pas la même, ainsi que le type bool qui n'existe pas je crois, le code compile avec un compilateur C... alors faut pas pousser

Absolument pas, c'est la dèche de comprendre la logique applicative.

Lisible c'est ça:

isNull :: Integer -> Bool
isNull = (== 0)
 
isMultiple :: Integer -> Integer -> Bool
isMultiple a b = isNull $ mod a b
 
sieve :: Integer -> [Integer]
sieve limit = 
    2 : (sieveHelper [3,5..limit])
 
sieveHelper :: [Integer] -> [Integer]
sieveHelper (x:xs) = 
    x:rest
     where
       rest = filter (not . (`isMultiple` x)) xs

Et en bonus ça écrase ton code en efficacité:

y'a qu'un autiste pour trouver ça lisible

pis c'est pas du C d'abors, tu va te faire engueuler toi aussi

sinon, ton algo, en français, ça donne quoi ? (parcequ'il a l'air un peu différent du mien, mais je pige pas une ligne sur 15

C'est une traduction directe du Crible en Haskell.

Je te le détaille dans un thread dédié dans la souscat FP, histoire de cesser le HS

edit: http://forum.hardware.fr/hfr/Progr [...] 3972_1.htm

Après correction de mon algo complètement pourri, finalement le crible d'eratosthene est infiniment meilleur que mon approche pourrie
 
Et C# défonce haskell (envirnon 5 fois plus rapide... jusqu'à ce qu'on arrive à plus de 10 000 000, là C# n'aime pas les gros tableaux et devient 3 fois plus lent )
 

Console.WriteLine("Da pas magic solution..." );
            {
                DateTime d1 = DateTime.Now;
                bool[] nbrs = new bool[val + 1];
                int maxi = val + 1;
 
                for (int i = 0; i < maxi; i++)
                {
                    nbrs[i] = true;
                }
 
                for (int i = 2; i < maxi; i++)
                {
                    for (int j = i * 2; j < maxi; j += i)
                    {
                        nbrs[j] = false;
                    }
                }
 
                for (int i = 2; i < maxi; i++)
                {
                    if (nbrs[i])
                    {
                        //Console.WriteLine(i);
                    }
                }
                                
                Console.WriteLine("Temps d'exécution : {0} ms", DateTime.Now.Subtract(d1).TotalMilliseconds);
            }

 
Et qu'on aille pas me dire que c'est du chinois pour ceux qui font du C

Le crible de machin c'est l'algo le plus rapide, point. Le seul inconvénient c'est qu'il n'est exploitable que pour les petits nombres (TRES petits) car extrêmement gourmand en mémoire.

Je crois que le  crible d'Atkin est normalement plus rapide, mais plus complexe (et c'est ne évolution du crible d'Eratosthène et pas un algo complètement différent)

Ici, ça va de 0 à 99.