Pacchetti corrotti [Aiuto soluzione]

Aiuto
1

Ciao a tutti,
stavo cercando di svolgere il problema https://training.olinfo.it/#/task/abc_checksum/statement, ma sono arrivato ad un punto fermo.
Ho pensato di calcolarmi i numeri primi fra 2 ed M con Eratostene, in questa maniera:

#include <cmath>
#include <vector>

const int MAXM = 4000000;



std::vector<int> primi;

std::vector<bool> e_primo (MAXM + 1, true);

void inizializza (int P, int M) {

    for (int i = 2; i <= M; i++) {

        if (e_primo[i]) {

            primi.push_back(i);

            if (i < sqrt(M))

                for (int j = i*i; j <= M; j +=i)

                    e_primo[j] = false;

        }

però dopo questo non ho idea di cosa fare nella funzione controlla, qualcuno mi può guidare?

2

In pratica per ogni parametro della funzione devi controllare che sia coprimo con tutti i parametri delle chiamate precedenti. Nel caso in cui non lo fosse significa che esiste almeno un primo p che divide sia il C attuale sia uno precedente. Puoi notare come il numero di fattori primi differenti che dividono un intero x è molto ridotto (inferiore a log_2x). Quindi puoi, per ogni primo mantenere uno dei C precedenti che è suo multiplo (se ne hai già incontrato uno) e quindi quando ottieni un nuovo C scomporlo nei fattori primi e controllare se qualcuno divideva anche uno dei valori delle chiamate precedenti.