Bon, comme je galère comme un noob et que mes potes normaliens se sont aussi cassé les dents sur ce problème (bon, peut-être que je le leur ai mal expliqué aussi), j’implore votre aide !

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 ?