Primo permissivo

Aiuto
1

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.

2

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

1 Mi Piace
3

Ti ringrazio, tuttavia lo faccio già. :sob:
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);
4

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)

1 Mi Piace
5

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

6

Risolto, grazie mille a tutti :smiley: