Crible d'Ératosthène — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 5)

Crible d'Ératosthène

Tableaux · niveau 2

Énoncé

Pour trouver tous les nombres premiers inférieurs à $n$ , on part d'un tableau de booléens premier[0..n-1] tous vrais ; on met $0$ et $1$ à faux ; puis, pour chaque $p$ encore marqué premier tel que $p \times p < n$ , on raye (met à faux) tous les multiples de $p$ à partir de $p \times p$ .

Écrire static boolean[] crible(int n).
Afficher les premiers inférieurs à $50$ , puis compter ceux qui sont inférieurs à un million.
Pourquoi peut-on commencer à rayer à $p \times p$ plutôt qu'à $2 p$ ?

Corrigé


static boolean[] crible(int n) {                 // premier[k] pour 0 <= k < n
    boolean[] premier = new boolean[n];
    Arrays.fill(premier, true);
    premier[0] = false;
    if (n > 1) premier[1] = false;
    for (int p = 2; p * p < n; p++) {
        if (premier[p]) {
            for (int m = p * p; m < n; m += p) premier[m] = false;
        }
    }
    return premier;
}


crible < 50 : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
premiers < 1 000 000 : 78498

Un multiple $k \times p$ avec $k < p$ a déjà été rayé lors du traitement du plus petit facteur premier de $k$ , qui est inférieur à $p$ . Le premier multiple de $p$ qui reste à rayer est donc $p \times p$ . Pour la même raison, on s'arrête dès que $p \times p \geq n$ : tous les nombres composés inférieurs à $n$ ont alors été rayés. Le crible traite un million de nombres en quelques millisecondes, bien plus vite que $1 0^{6}$ appels à estPremier.