Crible linéaire

L'objectif est de déterminer tous les nombres premiers jusqu'à une borne \(n\), avec \(n \le 10^8\). Le crible d'Ératosthène classique a une complexité de \(O(n \ln \ln n)\), car il marque les multiples de chaque nombre premier à plusieurs reprises. Pour une efficacité optimale, on utilise un crible linéaire où chaque nombre composé est marqué exactement une fois par son plus petit facteur premier. L'algorithme parcourt les entiers \(x\), puis pour chaque \(x\) itère sur les premiers \(p\) déjà trouvés ; si \(p\) divise \(x\), on arrête pour garantir que chaque composé est attribué à son plus petit diviseur premier.

const int BORNE = 1e8 + 5;
int n, estCompose[BORNE], premiers[BORNE], nbPremiers;

void initialiserCrible() {
    estCompose[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!estCompose[i]) {
            premiers[++nbPremiers] = i;
        }
        for (int j = 1; j <= nbPremiers && i * premiers[j] <= n; j++) {
            estCompose[i * premiers[j]] = 1;
            if (i % premiers[j] == 0) break;
        }
    }
}

Somme de préfixe de Dirichlet

Étant donné un tableau \(a\), on souhaite calculer un tableau \(b\) tel que \(b_x = \sum_{y \mid x} a_y\) pour \(n \le 2 \times 10^7\). Une approche directe serait \(O(n \ln n)\), ce qui est trop lent. En utilisant la convolution de Dirichlet, on interprète les fonctions arithmétiques : \(A * I = B\), où \(I\) est la fonction constante égale à 1. On décompose \(I\) en un produit de foncitons caractéristiques pour chaque nombre premier, ce qui permet de calculer la somme de manière incrémentale via un crible similaire à celui d'Ératosthène, réduisant la complexité à \(O(n \ln \ln n)\).

const int LIMITE = 2e7 + 5;
int n;
unsigned int donnees[LIMITE];
bool traite[LIMITE];

void calculerSommeDirichlet() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> donnees[i]; // Entrée des valeurs initiales
    for (int i = 1; i <= n; i++) traite[i] = false;
    unsigned int resultat = 0;
    for (int i = 1; i <= n; i++) {
        if (!traite[i]) {
            for (int j = 1; i * j <= n; j++) {
                donnees[i * j] += donnees[j];
                traite[i * j] = true;
            }
        }
        resultat ^= donnees[i];
    }
    cout << resultat << endl;
}

Bloc de division entière

On souhaite calculer la somme \(\sum_{i=1}^{n} d(i)\), où \(d(i)\) est le nombre de diviseurs de \(i\), pour \(n \le 10^{12}\). En transformant la somme, on obtient \(\sum_{i=1}^{n} \lfloor n / i \rfloor\). La fonction \(\lfloor n / i \rfloor\) ne prend que \(O(\sqrt{n})\) valeurs distinctes, et pour chaque valeur, les indices correspondants forment un intervalle continu. Pour chaque borne gauche \(l\), on détermine la borne droite \(r = \lfloor n / (n / l) \rfloor\), ce qui permet de calculer la contribution par bloc en \(O(\sqrt{n})\).

long long n, total;

void effectuerDivision() {
    cin >> n;
    total = 0;
    for (long long gauche = 1, droite; gauche <= n; gauche = droite + 1) {
        droite = n / (n / gauche);
        total += (droite - gauche + 1) * (n / gauche);
    }
    cout << total << endl;
}

Application de la fonction de Möbius

Exemple : pour des suites \(A\), \(B\), \(C\), calculer la somme \(\sum_{i=1}^{n} \sum_{j=1}^{n} A(i) B(j) C(\gcd(i, j))\) avec \(n \le 10^6\). On commence par isoler le PGCD : en posant \(g = \gcd(i, j)\), on effectue un changement de variable pour obtenir une expression impliquant la fonctoin de Möbius \(\mu\). Après réarrangeemnt, la somme se réécrit comme une convolution de Dirichlet entre \(C\) et \(\mu\), définissant une nouvelle fonction \(D(x) = \sum_{d \mid x} C(d) \mu(x/d)\). La somme finale s'exprime alors en fonction de \(D(k)\) et des sommes partielles de \(A\) et \(B\), pouvant être calculée en \(O(n \ln n)\) ou en \(O(n \ln \ln n)\) avec des optimisations adaptées.