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;
}
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