CHECKSUM:Execution Timeout e output errato

Ho fatto checksum, ma c’è un piccolo problema. Ho risolto per i casi di esempio ma per gli altri o va in overtime e l’output è sbagliato.
Riuscite ad aiutarmi?

#include <cmath>
#include <algorithm>
#include <math.h>

using namespace std;

int P, M,last=0;
int *vett=new int[300000];

void inizializza(int P, int M) {
    // Salviamo P e M in due variabili globali.

    ::P = P;

    ::M = M;



}


bool coprimi(int n, int m){
    int k=std::min(n,m);
    int d=2;
    if((n%k==0)&&(m%k==0))
        return false;
    if((n%d==0)&&(m%d==0))
        return false;
    for(d=3;d<=sqrt(n);d+=2){
        if((n%d==0)&&(m%d==0))
            return false;
    }
    return true;
}



int controlla(int checksum){
    vett[last]=checksum;
    if (checksum>M) {
        last++;
        return M;
    }
    for(int i=0;i<last;i++){
        if (coprimi(checksum,vett[i])!=true){
            last++;
            return vett[i];
        }
    }
    last++;
    return 0;
}

Grazie in anticipo

Allora da quello che ho capito tu di volta in volta aggiungi il numero all’array e controlli tra tutti i precedenti se la coppia é semiprima. Qui sta il problema degli output errati, infatti in caso un pacchetto precedente non é semiprima con quello attuale, ma non é stato preso (quindi non é stato stampato 0) non preclude l’affidabilità di quello attuale; per farti capire ti faccio un esempio:
5 15 3
L’output che stampi tu é:
0 5 15
Mentre quello corretto é:
0 5 0

Ora ragioniamo sulla complessità, ogni numero deve essere controllato con tutti gli altri numeri, quindi asintoticamente O(P^2), e ad ogni controllo ne calcoli tutti i fattori primi, quindi O(rad(M)) in totale O(P^2rad(M)) che con P che arriva a 10^5 e Mi a 10^6 é troppo. Il tuo approccio é quindi abbastanza sbagliato per ottenere 100/100.
Piuttosto che darti la soluzione un paio di hint:
Sarebbe interessante calcolare i primi una sola volta e non dover ciclare sui numeri che già conosciamo.
Poi dí come é andata

Non capisco cosa tu intenda quando mi dici che con 15 e 3 io non debba stampare 15, ma 0, perchè 3 non è coprimo con 15.

Appunto, ma a 15 non hai dato 0 e quindi non deve essere controllato