Problème — Le crible d'Ératosthène, et ce qu'il coûte

1. Le crible.

/* Renvoie un tableau c de n+1 booléens : c[k] vaut true ssi k est premier.
   L'appelant devra faire free. Précondition : n >= 1. */
bool* crible(int n) {
    assert(n >= 1);
    bool* c = malloc((size_t) (n + 1) * sizeof(bool));
    if (c == NULL) { return NULL; }
    c[0] = false;
    if (n >= 1) { c[1] = false; }
    for (int k = 2; k <= n; k = k + 1) { c[k] = true; }
    for (int p = 2; p * p <= n; p = p + 1) {
        if (c[p]) {
            for (int m = p * p; m <= n; m = m + p) { c[m] = false; }
        }
    }
    return c;
}

2. L'arrêt à $\sqrt{n}$. Si $k\le n$ est composé, il s'écrit $k=ab$ avec $2\le a\le b$. Alors $a^2\le ab=k\le n$, donc $a\le \sqrt{n}$. Tout composé possède donc un diviseur premier $\le \sqrt{n}$, et il aura été rayé lors du passage sur ce diviseur. Les $p>\sqrt{n}$ n'ont plus rien à rayer.

3. Le départ à $p^2$. Un multiple $mp$ avec $m<p$ possède un facteur $m$ dont le plus petit diviseur premier est $\le m<p$ : il a donc déjà été rayé lors d'un passage antérieur. Commencer à $p^2$ ne perd rien et évite de rayer plusieurs fois.

4. La complexité. Pour chaque premier $p\le \sqrt{n}$, la boucle intérieure fait environ $n/p$ tours. Le total est

$$\sum _{p\le \sqrt{n}\text{ premier}}\frac{n}{p}=n\sum _{p\le \sqrt{n}}\frac{1}{p}=\Theta (n\log \log n),$$

en admettant le résultat classique ${\sum }_{p\le x}1/p=\ln \ln x+O(1)$. En espace, le crible occupe $\Theta (n)$ octets.

Mise en garde sur p * p <= n. Le produit $p\times p$ est calculé en int. Pour $n$ proche de la capacité maximale, $p$ approche $\sqrt{n}$ et $p^2$ approche $n$ : cela tient. Mais la variante p <= sqrt(n) serait pire — elle appellerait une fonction flottante à chaque tour, avec les problèmes de précision du chapitre chap:algo-prog. On garde la forme entière.