### Project Euler - Problem 12

Inviato:

**23 giu 2009, 14:56**Cos'è "Project Euler" in due parole:

http://projecteuler.net/index.php

Passando al problema #12:

(premesso che lavoro in python) il mio tentativo di soluzione si basa semplicemente sulla definizione di una funzione div(n), che dato un intero n in input, dia in output il numero di suoi divisori: div(10) = 4.

In pratica dato n, se n è pari controlla per tutti numeri $ $x$ $ da 1 a $ $ \frac{n}{2}$ $ se $ $ n \equiv 0 \pmod x $ $. Se sì, allora aumenta il counter del numero dei divisori di 1. Se n è dispari, controlla i numeri da 1 a $ $ \lceil \tfrac{n}{2} \rceil $ $ ma saltando tutti i pari (x = 1,3,5...)

Fatto questo, la mia idea prevedeva di far controllare al programma tutti i valori di div(n(n+1)/2) per n =1,2,3... fino a quando div >= 500.

Fatto sta che il mio PC impiega circa 6 minuti a trovare il primo numero triangolare con div() > 150... e il tentativo per div() > 300 l'ho stoppato dopo decine di minuti. Eppure:

http://projecteuler.net/index.php

*Project Euler is a series of challenging mathematical/computer programming problems*Passando al problema #12:

*What is the value of the first triangle number to have***over**five hundred divisors?*Qual è il primo numero triangolare con*(compresi l'1 e se stesso).**più**di 500 divisori?(premesso che lavoro in python) il mio tentativo di soluzione si basa semplicemente sulla definizione di una funzione div(n), che dato un intero n in input, dia in output il numero di suoi divisori: div(10) = 4.

Codice: Seleziona tutto

```
def div(n):
ris = 1
if n%2 == 0:
for x in range(1, n/2+1):
if n%x == 0:
ris = ris + 1
return ris
else:
for x in range(1, int(math.ceil(n/2))+1, 2):
if n%x == 0:
ris = ris + 1
return ris
```

In pratica dato n, se n è pari controlla per tutti numeri $ $x$ $ da 1 a $ $ \frac{n}{2}$ $ se $ $ n \equiv 0 \pmod x $ $. Se sì, allora aumenta il counter del numero dei divisori di 1. Se n è dispari, controlla i numeri da 1 a $ $ \lceil \tfrac{n}{2} \rceil $ $ ma saltando tutti i pari (x = 1,3,5...)

Fatto questo, la mia idea prevedeva di far controllare al programma tutti i valori di div(n(n+1)/2) per n =1,2,3... fino a quando div >= 500.

Fatto sta che il mio PC impiega circa 6 minuti a trovare il primo numero triangolare con div() > 150... e il tentativo per div() > 300 l'ho stoppato dopo decine di minuti. Eppure:

Qualche consiglio su come gestire diversamente il problema, o come migliorare la funzione div()?an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.