# Primo permissivo

**URL:** <https://forum.olinfo.it/t/primo-permissivo/4254>\
**Category:** Aiuto\
**Created:** [28 Dicembre 2016, 9:09am UTC](https://forum.olinfo.it/t/primo-permissivo/4254 "2016-12-28T09:09:50Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![rego](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/e8c25b/32.png) [@rego](https://forum.olinfo.it/u/rego)\
**Post date:** [28 Dicembre 2016, 9:09am UTC](https://forum.olinfo.it/t/primo-permissivo/4254/1 "2016-12-28T09:09:51Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![arna1998](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/ea5d25/32.png) [@arna1998](https://forum.olinfo.it/u/arna1998)\
**Post date:** [28 Dicembre 2016, 12:50pm UTC](https://forum.olinfo.it/t/primo-permissivo/4254/2 "2016-12-28T12:50:02Z")

</div>

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](https://it.wikipedia.org/wiki/Crivello_di_Eratostene)

---

<div class="post-metadata">

**Author:** ![rego](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/e8c25b/32.png) [@rego](https://forum.olinfo.it/u/rego)\
**Post date:** [28 Dicembre 2016, 5:12pm UTC](https://forum.olinfo.it/t/primo-permissivo/4254/3 "2016-12-28T17:12:27Z")

</div>

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);
```

---

<div class="post-metadata">

**Author:** ![doublechar14](https://forum.olinfo.it/user_avatar/forum.olinfo.it/doublechar14/32/426_2.png) [@doublechar14](https://forum.olinfo.it/u/doublechar14)\
**Post date:** [28 Dicembre 2016, 5:20pm UTC](https://forum.olinfo.it/t/primo-permissivo/4254/4 "2016-12-28T17:20:44Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![arna1998](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/ea5d25/32.png) [@arna1998](https://forum.olinfo.it/u/arna1998)\
**Post date:** [28 Dicembre 2016, 6:35pm UTC](https://forum.olinfo.it/t/primo-permissivo/4254/5 "2016-12-28T18:35:44Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![rego](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/e8c25b/32.png) [@rego](https://forum.olinfo.it/u/rego)\
**Post date:** [29 Dicembre 2016, 8:01am UTC](https://forum.olinfo.it/t/primo-permissivo/4254/6 "2016-12-29T08:01:02Z")

</div>

Risolto, grazie mille a tutti 😃