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 12 440 fois - Téléchargée 17 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
cs_Julien39
Messages postés
6414
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
29 juillet 2020
 366
13 févr. 2010 à 08:14
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 ...
cs_Julien39
Messages postés
6414
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
29 juillet 2020
 366
13 févr. 2010 à 08:13
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 !
Virtuoooose
Messages postés
9
Date d'inscription
mardi 27 mai 2003
Statut
Membre
Dernière intervention
8 février 2009
5 févr. 2009 à 14:20
Merci de ton aide :)
cs_petifa
Messages postés
215
Date d'inscription
dimanche 20 février 2005
Statut
Membre
Dernière intervention
10 mars 2014
5 févr. 2009 à 14:18
certes mais bon au moins en faisant i+=2 tu accélère le processus
le résultat m'a l'air juste :p
Virtuoooose
Messages postés
9
Date d'inscription
mardi 27 mai 2003
Statut
Membre
Dernière intervention
8 février 2009
5 févr. 2009 à 14:08
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.
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.