Crible d'Ératosthène

Le 29 juin 2008 je racontais que j'avais écrit un programme très inefficace pour calculer la somme de tous les nombres premiers inférieurs à 2 000 000. Dans les commentaires, Guillaume écrivait qu'une manière beaucoup plus efficace aurait été d'utiliser le Crible d'Ératosthène. Je ne l'avais pas essayé, mais ça m'était resté dans la tête (en fait, j'ai appris et retenu le nom et la méthode).

Hier soir, passé minuit, je me suis dit que j'allais l'essayer, maintenant que je savais modestement faire des vecteurs en Java.


Le Crible (sans preuve)     La méthode est très simple. On se crée un tableau (dans sa tête, sur une feuille, whatever) où on écrit tous les entiers naturels de 2 à... au nombre que l'on souhaite utiliser pour limite (par exemple, 2 000 000). Ensuite, on prend le premier nombre du tableau (2), et on l'élève au carré (4). On biffe 4. On rajoute 2, et on biffe (6). On rajoute 2, et on biffe (8). Ainsi de suite, jusqu'à ce qu'on atteigne la limite (2 000 000).

On passe ensuite au prochain nombre pas biffé dans le tableau (3). On élève au carré (9), et on biffe. On rajoute 3 et on biffe (12). On rajoute 3 et on biffe (15). Ainsi de suite...

On prend le prochain nombre non rayé, à savoir 5. On l'élève au carré, ... etc.

On continue de même jusqu'à ce qu'on pogne le dernier entier non biffé plus petit que la racine de la limite (2 000 000).

Après tout ça, tous les nombres qui n'ont pas été rayés sont des nombres premiers. Extrêmement efficace, parce que ça ne fait pas juste déterminer si un certain nombre est premier... ça liste tous les nombres premiers en dessous d'une limite.

La page sur Wikipédia a même des images animées qui montrent comment ça marche.


J'ai tout programmé ça en Java hier soir, donc, sauf une petite chose (au lieu de "passer au prochain nombre non rayé", j'ai tout simplement fait tous les entiers). Temps d'exécution? Environ quoi... 5 secondes? Ma solution merveilleuse de fin juin avait pris 5 heures à rouler. Pour les intéressés, voici mon code ô combien merveilleux:

import java.lang.Math;   // pour Math.sqrt;

public class Crible {
   public static void main (String args[]) {
      final int LIMITE = 2000000;
      int t[] = new int[LIMITE];
      double somme = 0;
      for (int i = 1;i<=LIMITE;i++) {
         t[i-1] = i;
      }
      t[0] = 0;   // 1 n'est pas un nombre premier
      for (int i=2;i<=Math.sqrt(LIMITE);i++) {
         for (int j=i*i;j<=LIMITE;j+=i) {
            t[j-1] = 0;
         }
      }
      for (int i = 1;i<=LIMITE;i++) {
         somme += t[i-1];
      }
      System.out.println(somme);
   }
}