CRIBLE D'ERATOSTHENE
yvkoe
Messages postés
32
Date d'inscription
jeudi 20 septembre 2007
Statut
Membre
Dernière intervention
19 janvier 2009
-
10 oct. 2007 à 16:58
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 - 26 mai 2018 à 08:26
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 - 26 mai 2018 à 08:26
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/44331-crible-d-eratosthene
https://codes-sources.commentcamarche.net/source/44331-crible-d-eratosthene
26 mai 2018 à 08:26
Ton algorithme fonctionne certainement, je ne me suis pas amusé à l'essayer. Cependant ce que tu décris n'est pas un crible d'Erathostène voir wikipédia
https://fr.wikipedia.org/wiki/Crible_d'Ératosthène
Modifié le 26 mai 2018 à 10:19
Alors j'ai lu et relu ton code, et j'ai pas tout compris, pour ne pas dire, rien compris... Il y a un module 13 qui traine. Tu décales toutes listes de 1 ou 2 éléments... C'est pas facile à comprendre et pourtant l'énoncé est simple...Je ne comprends pas non plus pourquoi tu n'écris aucune fonction ? C'est bien jolie d'écrire sur du langage de haut niveau mais a quoi bon si c'est pour écrire comme en bas niveau...
Mais après tout ca à l'air de marcher, donc tant mieux !
Je sais que ce topic est vieux mais au moins les personnes qui tomberont dessus pourron trouver d'autres versions...
Pour rappel :
Le but du crible d'Erathostène est de trouver la liste des nombres premier qui sont inférieurs à un nombre N fixé par la personne.
Pour cela, différents algorithmes existent, dont un qui est simple et rapide :
Par définition un nombre est premier, si tous les nombres premier inférieurs ou égaux à sa racine ne le divise pas.
Exemple:
Autrement dit, pour tester si 100 est premier il faut tester tous les nombres premiers inférieurs ou égaux à sa racine donc inférieur ou égaux à 10. (2,3,5,7). Il faudra donc tester si 2 le divise puis 3 etc. On s'arretera bien évidemment à 2 car deux divise 100. (2x50=100)
De une cet algorithme est beaucoup plus rapide en terme de calcul pour l'ordinateur, et de deux l'algo est beaucoup plus simple. Mon code ne fait que quelques lignes... (44 dont 17 de commentaires...)
Voilà mon code si certains sont intéressés :
import java.util.*; public class HelloWorld{ // test si un nombre "nb" est premier SI oui il l'ajoute a la liste "crible" public static ArrayList<Integer> isPrime(int nb,ArrayList<Integer> crible){ // On pourcourt le crible jusqu'à atteindre le nombre inférieur ou égal à racine carré du nb testé for(int counter=0;counter<(crible.size()) && crible.get(counter)<=Math.sqrt(nb);counter++){ // si le nombre est divisible par un des nombres premier parcouru if(nb%(crible.get(counter))==0){ // alors on retourne le crible tel quel, autrement le nombre "nb" testé n'est pas premier return crible; } } // sinon on attends d'avoir parcouru toute la liste et si tout a été parcouru jusqu'a racine carré de nb alors le nombre est premier et on peut l'ajouter au crible et renvoyer le crible crible.add(nb); return crible; } public static void main(String []args){ ////////////////////////Définition des variables///////////////////////////////// ArrayList<Integer> crible=new ArrayList<Integer>();//liste des nombres premier crible.add(2);// on initialise le tableau des nombres premier avec le premier nombre premier (2) // nous cherchons tous les nombres premier inférieur à "numberlimit" int numberLimit=99; // METTEZ LA VALEUR SOUHAITEE // nous commencons à chercher à partir de 3 car 2 est déjà dans la liste jusqu'a numberLimit for(int nb_test=3;nb_test<=numberLimit;nb_test++){ //crible recoit crible + le nouveau nombre "nb_test" si celui est premier crible=isPrime(nb_test,crible); } // affichage for(int i=0; i<crible.size(); i++){ System.out.print(crible.get(i) + " "); //tous les 5 nombres on fait un retour à la ligne if(i%5==0)System.out.println(); } // j'ai laissé cette ligne pour afficher le dernier nombre premier de la liste car parfois la liste est trop longue et l'affichage peut bugué //System.out.print(crible.get(crible.size()-1) + " "); } }Explications disponibles ici : ICI
Merci d'y penser dans tes prochains messages.
22 oct. 2007 à 13:06
- Trouver les n premiers nombres premiers ou
- Savoir si un nombre est premier.
Dans l'absolu, ce genre d'algo n'est pas tres utile a part pour se faire la main ou se taper la bourre entre potes (genre "celui qui va calculer le plus vite les nombres premiers < 1000000" :o) ).
Sinon, si tu as vraiment besoin de savoir rapidement si des nombres sont premiers, tu peux preconstruire une liste en memoire pour quelques centaines de kilo et chercher dedans par dicotomie (ou bien carrement un gros tableau de booleens :o) ). C'est moins cool, mais beaucoup plus efficace...
Eric
19 oct. 2007 à 15:23
Bonjour à tous
merci Yvkoe pour la note et merci ltb69 et LEFAUVE42 pour les remarques.
C vrai, mais si on veut aller plus loin dans notre optimisation ... il suffit de combiner plusieurs théorèmes.
Par exemple, le plus facile et immediat, serait d'appliquer le théoreme (conséquence du théoreme de Bertrand) suivant :
un nombre naturel n qui n'est divisible par aucun nombre premier p <= racine(n) est automatiquement lui-même premier.
Il est inutile, donc, de prolonger les recherches au-delà de racine de n. Il suffit d'atteindre le dernier nbre premier (p) telque p<=racine(borne superieure choisie) pour sortir de la boucle ...(ça tombe bien : par defaut le tableau est à true, donc à la sortie selon cette condition on aura nos nbres premiers jusqu'à la borne_sup).
exemple : borne_sup =100 donc il suffit de terminer le crible au nombre 7 !
Sauf que l'affichage devra se faire en dehors de la boucle ...
voici le code modifié :
class Eratosthene {
/*Recherche des nombres tels qu'ils ne sont divisibles
que par eux même (ou 1!)*/
public static void main (String args[]) {
int i,j,borne_sup=35100,nbr_int_premier=0;
boolean []tableau_premiers = new boolean [borne_sup-1];
for (i=0;i<=tableau_premiers.length-1;i++)
{
tableau_premiers[i]=true;
}
// le chiffre 2 est premier "par defaut", d'ailleurs, tous au debut.
for (i=2;i*i<=borne_sup;i++) // i<=racine(borne_sup)
{
if (tableau_premiers[i-2]==true){ // bypass les nbres non 1ers
j=i+1;
while (j<=borne_sup)
{
if ((j%i)==0) tableau_premiers[j-2]=false;
j++;
}
// nbr_int_premier++;
// if (nbr_int_premier%13!=0) System.out.print(i+" ");
// else System.out.println(i+" ");
}
}
for (i=0;i<=tableau_premiers.length-1;i++)
{
if (tableau_premiers[i]==true)
{
nbr_int_premier++;
if (nbr_int_premier%13!=0) System.out.print(i+2+" ");
else System.out.println(i+2+" ");
}
}
System.out.println("");
System.out.println("Nomre de nbr premiers : "+nbr_int_premier+" entre "+2+" et "+borne_sup);
}
}
17 oct. 2007 à 11:21
Le crible est une bonne methode si tu veux obtenir rapidement tous les nombres premiers de 1 a n.
Cependant, il est possible de l'optimiser de plusieurs manieres.
La plus importante (et la plus simple) est de virer tous les nombres pairs de ton tableau.
En clair, tu commences a 1, et pour les nombres i que tu trouves, le nombre premier correspondant est (2*i)+1.
Ca te permet entre autre d'utiliser un tableau de booleens deux fois plus petits pour obtenir les memes resultats.
Sinon tu remarqueras si tu fais un peu de bench que les premieres iterations sont les plus longues.
De plus, ton tableau contient toujours une "pattern" qui se repete jusqu'a la fin.
Cette "pattern" est tres courte au debut, donc, tu peux preremplir ton tableau avec la pattern des 6 ou 7 premieres iterations par exemple, ce qui devrait diviser encore par 4 ou 5 le temps de calcul total.
Eric
16 oct. 2007 à 12:49
- Tu déclare la variable du compteur (i) en début de méthode. Il est plus clair de la mettre directement dans le for => en plus çà évite les effets de bord si tu veux réutiliser la variable
- Tu fais des tas de calcul, pour ne utiliser le tableau dans sa totalité (les "-2" qui trainent) => pourquoi ne pas plutôt perdre les deux premières cases (0 et 1). le code serait plus clair.
- Tu utilise -1 dans les conditions d'arrêt des for ( par ex i<=tableau_premiers.length-1). Par habitude, j'utilise plutôt : i<tableau_premiers.length. La condition d'arrêt est calculée à chaque boucle.
L'inconvénient de ta méthodes est qu'elle est de complexité n² => Pour tous les chiffres, tu reparcours tout les chiffres suivant (même si tu ne fais pas d'action) ==> somme ==> n²/2
Il vaudrait mieux du code en complexite n (lineaire) du style :
for (i = 2; i <= borne_sup; i++)
{
if (tableau_premiers[i])
{ // bypass les nbres non 1ers
mult = 2;
toto = i * mult;
while (toto <= borne_sup)
{
tableau_premiers[(int) toto] = false;
mult++;
toto = i * mult;
}
}
}
Pour info, on obtient un temps équivalent (8-9s), pour les nombres entre 2 à 10000, pour 50 appels à ta méthode ou 15000 appels de l'autre version.
Quant à lequel de tes deux algo est le plus rapide ... je dirais qu'ils se valent en performance pur, si ce n'est qu'ici tu fait l'impasse sur pas mal de calcul. Tu passes, en gros, de 10000² à 1229² (soit de 100000000 à 1510441 soit un gros facteur 60). En améliorant la complexité, tu as en plus un facteur 300.
Comme me disais un prof : Il vaut mieux améliorer la complexité de l'algo plutôt que l'algo lui même.
12 oct. 2007 à 11:40
Je trouve que tes codes sont originaux et que tu creuses plus avant même quand le premier code posté est satisfaisant(cf Nbres premiers)
Une question: tu bosses pour le moment...?
10 oct. 2007 à 16:58
très classe ,c'est important, la technique est primordiale mais après il faut sortir des chantiers battus.
Et là c'est le cas
Bravo!