Ciao a tutti,
come posso velocizzare l’algoritmo per risolvere il problema primo permissivo?
Ho provato una decina di algoritmi diversi, ma non riesco a capire come ottimizzare i tempi in merito al controllo sul fatto che un numero sia primo o meno.
Invece che controllare ogni volta se un numero è primo o meno potresti trovare tutti i numeri primi che possono essere coinvolti nel problema, in modo che successivamente puoi controllare se un numero è primo in tempo costante.
Potrebbe esserti utile questo: Crivello di Eratostene
Ti ringrazio, tuttavia lo faccio già.
Probabilmente c’è un modo più veloce per costruire la lista di numeri primi, non so.
for(i=3;i<=nmax;i=i+2){
primi.push_back(i);
}
it=primi.begin();
do{
jt=it;
jt++;
while(jt!=primi.end()){
if(*jt % *it ==0){
jt=primi.erase(jt);
continue;
}
jt++;
}
it++;
}while(*it<nmax/2);
Usa una matrice, non ricordo qual è il limite ma io l’ho definita così
bool N[10000000];
così da vedere se l’i-esimo numero è primo (true) o falso (false)
Salvandoti i primi in questo modo ogni volta devi scorrere l’array per verificare se un numero è primo, mentre se fai come ha detto @doublechar14 non devi scorrere e quindi risparmi in tempo
Risolto, grazie mille a tutti