22

Alors déjà ça ne sert à rien de calculer une racine carrée pour une boucle i<=sqrt(n), parce que ça revient au même que i*i<=n, de plus, sur une machine où les multiplications sont lentes, une boucle for (i=0; i*i<=n; i++) est plus rapide si elle est notée: for (i=i2=0; i2<=n; i2+=i,i++,i2+=i).

Ensuite, je signale qu'il existe la propriété que divisors(ab)=divisors(a)divisors(b) si pgcd(a,b)=1.

Or, pgcd(i,i+1)=1 pour tout i, donc divisors(i(i+1))=divisors(i)divisors(i+1). De plus, soit i(i+1)=2mjj impair et m entier. Alors divisors(i(i+1)/2)=divisors(2m-1j)=divisors(2m-1)divisors(j)=divisors(2m-1)divisors(i(i+1))/divisors(2m)=m divisors(i(i+1))/(m+1). Et m peut se trouver facilement à l'aide d'opérations sur les bits.

Bref, on peut aller beaucoup plus vite en appliquant un peu de Mathématiques (comme partout dans Project Euler).

Et puis, bref, ENS sux, Uni Wien rulez! tongue
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité