h3. Indicaţii de rezolvare

O soluţie brută, care parcurge toate numerele de la $1$ la $n$ ar trebui să obţină aproximativ $30$ de puncte.

O soluţie brută, care parcurge toate numerele de la $1$ la $n$ şi numără toţi divizorii ar trebui să obţină aproximativ $30$ de puncte.

Din descompunerea numărului în factori primi se pot calcula atât suma, cât şi numărul de divizori astfel: dacă $n = p{~1~}^d{~1~}^*p{~2~}^d{~2~}^*...*p{~k~}^d{~k~}^$, atunci numărul de divizori este egal cu $(d{~1~}+1)*(d{~2~}+1)*...*(d{~k~}+1)$.

Din descompunerea numărului în factori primi se pot calcula atât suma, cât şi numărul de divizori astfel: dacă <tex>n = p_{1}^{d_{1}}*p_{2}^{d_{2}}*...*p_{k}^{d_{k}}</tex>, atunci numărul de divizori este egal cu <tex>(d_{1}+1)*(d_{2}+1)*...*(d_{k}+1)</tex>, iar suma lor <tex>\frac{p_{1}^{d_{1}+1}-1}{p_{1}-1}*\frac{p_{2}^{d_{2}+1}-1}{p_{2}-1}*...*\frac{p_{k}^{d_{k}+1}-1}{p_{k}-1}</tex>

== include(page="template/taskfooter" task_id="ssnd") ==