CALCUL DES NOMBRES PREMIERS PAR LA CRIBLE D'ÉRATOSTHÈNE
billou_13
Messages postés
860
Date d'inscription
jeudi 4 mars 2004
Statut
Membre
Dernière intervention
19 août 2014
-
3 déc. 2007 à 09:17
cs_Malkuth Messages postés 268 Date d'inscription samedi 22 février 2003 Statut Membre Dernière intervention 24 avril 2013 - 3 déc. 2007 à 19:01
cs_Malkuth Messages postés 268 Date d'inscription samedi 22 février 2003 Statut Membre Dernière intervention 24 avril 2013 - 3 déc. 2007 à 19:01
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/44893-calcul-des-nombres-premiers-par-la-crible-d-eratosthene
https://codes-sources.commentcamarche.net/source/44893-calcul-des-nombres-premiers-par-la-crible-d-eratosthene
3 déc. 2007 à 19:01
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; ) ;
3 déc. 2007 à 17:40
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
3 déc. 2007 à 16:48
{
....
}
Cette condition n'est plus néscessaire car i*i est toujours inférieur a max dans la premiére boucle.
3 déc. 2007 à 15:55
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.
3 déc. 2007 à 15:20
3 déc. 2007 à 15:17
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.
3 déc. 2007 à 12:44
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 ... :-/
3 déc. 2007 à 12:22
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 ...)
3 déc. 2007 à 11:04
@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 ;-)
3 déc. 2007 à 09:54
plus lent?
3 déc. 2007 à 09:17
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 ^^