Le problème à résoudre est donné ici : http://projecteuler.net/index.php?section=problems&id=12
Mon implémentation naïve, en O(N²), en C :
#include <stdio.h>
int divisors(long n)
{
int d = 0;
long i = 1;
while (i <= n / 2) {
if (n % i == 0)
d++;
i++;
}
return d + 1;
}
long euler12()
{
long n = 1;
long i = 2;
while (divisors(n) < 500) {
n += i;
i++;
}
return n;
}
int main(int argc, char *argv[])
{
printf("%ld\n", euler12());
}
Quand, à la place du 500, je mets 300, ça va encore, mais dès que je dépasse 320 mon PC explose… Je me dis qu’il doit donc y avoir des astuces arithmétiques pour simplifier les calculs.
Les nombres dont on cherche à connaître le nombre de diviseurs sont de la forme
, peut-être que ça peut simplifier le calcul du nombre de diviseurs ?
De même, ma stratégie pour calculer le nombre de diviseurs d’un nombre n est très naïve, elle consiste simplement à essayer tous les nombres entre 1 et n / 2, il y a peut-être moyen d’aller plus vite ?
)
)
