1. Accueil
  2. Tous les snippets
  3. Snippets Java
  4. Nombres premiers par le crible d'eratosthène version optimisée

Nombres premiers par le crible d'eratosthène version optimisée

Soyez le premier à donner votre avis sur cette source.

Snippet vu 10 624 fois - Téléchargée 15 fois

Commenter

Contenu du snippet

Pour trouver tous les nombres premiers de 2 à Max, le principe est le suivant :
1. Construire l'ensemble de tous les entiers de 2 à Max
2. Extraire et afficher le plus petit élément de l'ensemble car c'est un nombre premier
3. Enlever de l'ensemble tous les multiples de ce nombre premier
4. Revenir à l'étape 2 jusqu'à ce que l'ensemble soit vide.

Source / Exemple : 


public class Main {

    public static void main(String[] args) {
        afficherNombresPremiers(100);
    }

    public static void afficherNombresPremiers(int n) {
        System.out.println("Les nombre premier de 0 à " + n + " sont :");
        boolean[] tab = new boolean[n + 1];
        //initialisation du tableau
        for (int i = 0; i <= n; i++) {
            tab[i] = true;
        }
        //on retire les nombres impaires
        for (int i = 4; i <= n; i += 2) {
            tab[i] = false;
        }
        // on sait déja que 2 est premier :
        // car tab[2] = true;
        System.out.println("2");

        for (int i = 3; i <= n; i += 2) {
            // on utilise des pas de 2, car tout les nombres pairs ne sont pas premiers.
            if (tab[i] == true) {
                System.out.println(i);
                for (int j = i; j <= n; j += i) {
                    tab[j] = false;
                }
            }
        }
    }
}

A voir également

Ajouter un commentaire

Commentaires

Signaler
Messages postés
6414
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
29 juillet 2020
 294
Et ausi, c'est une drôle d'idée de stocker les boolées dans un tableau, ca t'oblige a reparcourir ton tableau à la fin ...
Signaler
Messages postés
6414
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
29 juillet 2020
 294
De toutes petites améliorations te permetraient d'accélérer considérablement le programme, tu n'est pas obligé de tester les nombres jusqu'ç n, tu peux t'arreter à racine de n, si un nombre n'est pas premier, il adment un diviseur plus petit que ca racine.

Ensuite, tu pourrais stocker les nombres premiers que tu as trouvé dans une liste et ne tester la division que pour ces nombres là, au lieu de retirer les multiples de deux, tu retire tout les nombres composés.

Ce n'est qu'un début mais avec ta méthode pour savoir si 101 est premier, tu vas effectuer 50 calculs, en ajoutant les améliorations que je te propose, tu ne feras que 4 calculs, tu vas apeu pres diviser le temps d'éxécution par 10 !
Signaler
Messages postés
9
Date d'inscription
mardi 27 mai 2003
Statut
Membre
Dernière intervention
8 février 2009
Merci de ton aide :)
Signaler
Messages postés
215
Date d'inscription
dimanche 20 février 2005
Statut
Membre
Dernière intervention
10 mars 2014
certes mais bon au moins en faisant i+=2 tu accélère le processus
le résultat m'a l'air juste :p
Signaler
Messages postés
9
Date d'inscription
mardi 27 mai 2003
Statut
Membre
Dernière intervention
8 février 2009
Bon la c'est bon (enfin) , c'est juste que je voulais éviter deux faire 2 boucles for d'affilés pour l'initialisation du tableau mais c'est vrai qu'on peux pas trop faire autrement.
Afficher les 12 commentaires
S'inscrire maintenant

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.