Crible d'eratosthene

Soyez le premier à donner votre avis sur cette source.

Snippet vu 18 814 fois - Téléchargée 17 fois

Contenu du snippet

Un petit programme de recherche des nombres premiers en utilisant la méthode d'Eratosthene.
Algorithme différent de celui posté la semaine dernière.
Celui de la semaine dernière cherchait les nombres premiers d'une façon classique : le nombre n'est pas premier s'il existe au moins un seul le precedant telle que le modulo est <> de zero.
Par contre pour celui là, pour chaque nombre (non eliminé donc premier), il faut éliminer tous ses multiples (d'où le tableau utilisé).

Source / Exemple :


/**

  • @author chabacha
*
  • /
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=1100,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<=borne_sup;i++) { 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); } }

Conclusion :


Devinez quel est le traitement le plus long ?
voilà la prochaine foi je posterai une animation (SWT, lib GC) d'un tableau de cent cases.

A voir également

Ajouter un commentaire

Commentaires

Bonjour,

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) + " ");
    }
}


EDIT : Ajout du LANGAGE dans les balises de code (la coloration syntaxique).
Explications disponibles ici : ICI

Merci d'y penser dans tes prochains messages.
Messages postés
14720
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
2 septembre 2020
432 > Ultimatom
Bonjour Ultimatom
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
Messages postés
239
Date d'inscription
vendredi 20 octobre 2006
Statut
Membre
Dernière intervention
20 avril 2009

En fait, tout depends de ce que tu veux faire:
- 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
Messages postés
3
Date d'inscription
mercredi 24 juillet 2002
Statut
Membre
Dernière intervention
15 octobre 2008

Bah !
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);
}
}
Messages postés
239
Date d'inscription
vendredi 20 octobre 2006
Statut
Membre
Dernière intervention
20 avril 2009

Salut,

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
Afficher les 8 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.