# Complessità computazionale di abc\_checksum

**URL:** <https://forum.olinfo.it/t/complessita-computazionale-di-abc-checksum/4670>\
**Category:** Algoritmi\
**Created:** [13 Giugno 2017, 8:04am UTC](https://forum.olinfo.it/t/complessita-computazionale-di-abc-checksum/4670 "2017-06-13T08:04:20Z")\
**Posts on this page:** 3\
**Page:** 2

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [16 Giugno 2017, 7:32am UTC](https://forum.olinfo.it/t/complessita-computazionale-di-abc-checksum/4670/21 "2017-06-16T07:32:03Z")

</div>

Sono d’accordo con il tuo spoiler, però quando P \> π(M) penso che a quella sommatoria vada aggiunto un numero P-π(M) di primi che, se tutti uguali al primo più grande minore di M, ci “costringono” a eseguire π(M) volte `gcd()` - prima avevo erroneamente usato M al posto di P.

Poi ovvio che ad esempio con O(M) memoria possiamo evitare di controllare due volte lo steso numero 🙂

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [30 Giugno 2017, 2:20pm UTC](https://forum.olinfo.it/t/complessita-computazionale-di-abc-checksum/4670/22 "2017-06-30T14:20:31Z")

</div>

Ciao,  
scusami per l’estremo ritardo con cui arriva questa risposta. (La buona notizia è che le soluzioni della gara sono quasi pronte).

> [@filippos](#):
>
> quando P\>π(M)

Ma è possibile che ciò accada? Una delle assunzioni specificava “I valori di checksum sono tutti diversi”. Questo dovrebbe escludere il caso che tu presenti, o sbaglio?

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [1 Luglio 2017, 11:07am UTC](https://forum.olinfo.it/t/complessita-computazionale-di-abc-checksum/4670/23 "2017-07-01T11:07:52Z")

</div>

> [@lucach](#):
>
> Ma è possibile che ciò accada? Una delle assunzioni specificava “I valori di checksum sono tutti diversi”. Questo dovrebbe escludere il caso che tu presenti, o sbaglio?

Si esatto, me l’ero persa 🙂

[Pagina precedente](https://forum.olinfo.it/t/complessita-computazionale-di-abc-checksum/4670.md?page=1)