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

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

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.