RECHERCHE DE NOMBRES PREMIERS PAR LE CRIBLE D'ERATOSTHENE
_michel
Messages postés
77
Date d'inscription
mardi 27 juin 2006
Statut
Membre
Dernière intervention
12 août 2010
-
27 juin 2006 à 14:34
ncoder Messages postés 244 Date d'inscription vendredi 6 mai 2005 Statut Membre Dernière intervention 6 avril 2008 - 29 juin 2006 à 13:38
ncoder Messages postés 244 Date d'inscription vendredi 6 mai 2005 Statut Membre Dernière intervention 6 avril 2008 - 29 juin 2006 à 13:38
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/38335-recherche-de-nombres-premiers-par-le-crible-d-eratosthene
https://codes-sources.commentcamarche.net/source/38335-recherche-de-nombres-premiers-par-le-crible-d-eratosthene
29 juin 2006 à 13:38
http://www.cppfrance.com/codes/NOMBRES-PREMIERS-CRIBLE-ERATHOSTENE_24873.aspx
http://www.cppfrance.com/codes/RECHERCHE-NOMBRES-PREMIERS-AVEC-CRIBLE-ERATOSTHENE_9715.aspx
ou encore
http://www.cppfrance.com/codes/CRIBLE-ERATOSTHENE_10945.aspx
A+ bonne programmation
29 juin 2006 à 12:55
En mémoire, en ne stockant qu'un nombre sur 2, les nombres impairs (ne pas oublier 2).
En temps, il faut remplacer :
-les pow(2,x%8) par 1<<(x&7)
-les x/8 par x>>3
-à part pour 2, on peut utiliser une incrément de j qui est 2*i
-on peut commencer pour j à i*i
-plus compliqué qu'au dessus, prendre une variable qui contient j/8, et une autre j%8, et à chaque fois, ajouter i%8, sur la variable de j%8 et si c'est >8, enlever 8 à cette variable et incrémenter l'autre (valable pour la version qui utilise les nb pairs et impairs, à modifier pour l'autre).
Avec ça, on peut aller beaucoup plus loin que 100000. (le record est 10^16)
Autre optimisation algorithmique : utiliser le crible d'Atkin.
Pole.
29 juin 2006 à 12:30
D'abord merci d'avoir conservé cette source, cela me permettra de faire progresser l'algorythme, si c'est encore possible.
Ensuite, j'ai moi-même recherché, sur la totalité des codes sources, ceux qui font référence à premier, premiers, Eratosthène...
Je n'ai trouvé que le mien en C, me serais-je trompé dans ma recherche ?
Si c'est le cas, veuiller m'indiquer ceux que je n'ai pas su trouver, afin de m'en inspirer si c'est utile.
Enfin, je reconnais que j'étais bien conscient que ma source était destinée à être supprimer, en revanche je voulais bénéficier du surcis pour connaitre l'avis d'autres developpeurs, et mes mises à jours n'ont eu pour but que de leurs présenter la version la plus récente, et de corriger de nombreuses fautes d'orthographes.
Salutations.
28 juin 2006 à 18:05
une prochaine fois évite les mises à jour si j'ai indiqué que ça ne sera pas conservé, ce serait perdre du temps.
Je vais donc exceptionnellement laisser cette source mais rappelle toi bien à l'avenir de controler que le sujet n'est pas déjà traité en de nombreux exemplaires parce qua ce sera suppression à tout coup, la place sur nos serveurs n'est pas infinie.
Bonne continuation.
28 juin 2006 à 16:34
Pour ceux qui ne savent pas comment on fait , on tape :
"premier > fichier.txt"
au lieu
"premier"
L'inconvénient est qu'on ne peut pas executer le programme de l'explorateur Windows, mais à partir d'une invite de commande.
28 juin 2006 à 16:15
Si les seuls diviseurs sont 1 et ce nombre, il est premier.
28 juin 2006 à 16:08
28 juin 2006 à 14:37
28 juin 2006 à 10:01
Tab[i] = i + 2;
for (i=2; i<Taille/2; i++)
{
if (!Tab[i])
continue;
for (j=i*2; j<Taille; j += i)
{
if (Tab[j])
Tab[j] = 0;
}
}
voila le bout de code que j'avais du utiliser pour calculer les nombres premiers. Si ca peut servir...
27 juin 2006 à 18:00
http://www.google.com/custom?domains=cppfrance.com&q=premier&sa=Rechercher&sitesearch=cppfrance.com
Ne sera pas conservé.
27 juin 2006 à 15:06
27 juin 2006 à 14:46
On part d'une liste
2 3 4 5 6 7 8 9 10
On prend le premier nombre : 2->1 er nombre premier
On l'enlève.
On enlève tous ses multiples.
3 5 7 9
On prend le premier nombre : 3-2ème nombre premier
On l'enlève.
On enlève tous ses multiples.
5 7
5 est plus grand que la racine carré de 10, on stoppe.
Normalement pour l'implémentation, on prend une liste qu'on a mis à 0, et à chaque fois qu'on effectue l'opération on enlève, on met la case correspondante à 1. Pour prendre le premier nombre, on recherche le premier nombre != 0.
Pole.
27 juin 2006 à 14:34
Merci de me donner des conseils.