Compter les nombres premiers — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 15)

Compter les nombres premiers

Threads · niveau 2

Énoncé

Compter les nombres premiers inférieurs à $2000000$ avec un pool de quatre fils : découper l'intervalle en tranches de $250000$ , soumettre une Callable<Integer> par tranche, puis additionner les résultats des Future. Pourquoi des tranches de même taille n'ont-elles pas toutes la même durée ?

Corrigé


final int N = 2_000_000, TRANCHE = 250_000;
ExecutorService pool = Executors.newFixedThreadPool(4);
List<Future<Integer>> futurs = new ArrayList<>();
for (int de = 0; de < N; de += TRANCHE) {
    int debut = de, fin = Math.min(de + TRANCHE, N);          // tranche [debut, fin)
    futurs.add(pool.submit(() -> {
        int c = 0;
        for (int n = debut; n < fin; n++) if (premier(n)) c++;
        return c;
    }));
}
int total = 0;
for (Future<Integer> f : futurs) total += f.get();
pool.shutdown();
System.out.println(futurs.size() + " tâches, " + total + " nombres premiers inférieurs à " + N);

avec premier(n) qui teste les diviseurs $d$ tels que $d^{2} \leq n$ .


8 tâches, 148933 nombres premiers inférieurs à 2000000

Le test d'un nombre premier $n$ coûte environ $n$ divisions : les tranches des grands nombres sont plus longues à traiter. C'est l'intérêt de soumettre plus de tâches (huit) qu'il n'y a de fils (quatre) : un fil qui finit tôt prend la tâche suivante, et la charge s'équilibre.