Énoncé du problème

Soit \(n\) la longueur d'une suite \((a_i)\) définie ainsi :

• \(a_1\) est le \(n\)-ième nombre premier.
• Pour \(i \ge 2\), la différence \(a_i - a_{i-1}\) est le \(i\)-ème nombre premier en partant de la fin (c'est-à-dire le \((n-i+1)\)-ième nombre premier).

On demande la somme de tous les termes de cette suite. Approche

Avec \(n \le 10000\), le \(n\)-ième nombre premier est \(104729\). Une génération naïve des premiers serait trop lente. On utilise donc un crible linéaire (crible d'Euler) de complexité \(O(N)\) pour obtenir tous les nombres premiers jusqu'à \(104729\).

Ensuite, on construit la suite \((a_i)\) en accumulant les premiers dans l'ordre décroissant : chaque \(a_i\) vaut la somme des \(i\) derniers premiers (du \(n\)-ième jusqu'au \((n-i+1)\)-ième). La somme demandée est alors la somme de ces valeurs \(a_i\).

Implémentation du crible linéaire

L'idée est de marquer chaque nombre composé exactement une fois, en parcourant les entiers de 2 à la limite et en arrêtant dès qu'un multiple du premier courant est détecté.

const int MAX = 104730;
vector<bool> estComposite(MAX, false);
vector<int> premiers;
premiers.reserve(10000);

for (int i = 2; i < MAX; ++i) {
    if (!estComposite[i])
        premiers.push_back(i);
    for (int p : premiers) {
        if (i * p >= MAX) break;
        estComposite[i * p] = true;
        if (i % p == 0) break;
    }
}

Calcul de la somme

On dispose maintenant de la liste des premiers (indexée à partir de 0). La suite \((a_i)\) se construit en ajoutant successivement les premiers dans l'ordre inverse :

long long somme = 0;
long long accumulateur = 0;
for (int i = n - 1; i >= 0; --i) {
    accumulateur += premiers[i];
    somme += accumulateur;
}

\(n\) étant le nombre de termes (donné en entrée). La variable accumulateur contient successivement \(a_1, a_2, \dots, a_n\) et somme en est la somme totale.

Code complet

#include <iostream>
#include <vector>
using namespace std;

int main() {
    const int MAX = 104730;
    vector<bool> estComposite(MAX, false);
    vector<int> premiers;
    premiers.reserve(10000);

    for (int i = 2; i < MAX; ++i) {
        if (!estComposite[i])
            premiers.push_back(i);
        for (int p : premiers) {
            if (i * p >= MAX) break;
            estComposite[i * p] = true;
            if (i % p == 0) break;
        }
    }

    int n;
    cin >> n;

    long long somme = 0;
    long long accu = 0;
    for (int i = n - 1; i >= 0; --i) {
        accu += premiers[i];
        somme += accu;
    }
    cout << somme << endl;
    return 0;
}