Plus grand diviseur premier d’un nombre

J'ai beaucoup plus lutté sur le troisième problème, qui est essentiellement dû au temps de calcul en O(n^2). Bon, et puis mon code est littéralement farci de logs pour me permettre de savoir à quelle vitesse je vais.

Ici, il n'y a pas vraiment de trucs spécifiques groovy, mais plutôt une sacré optimisation basée sur la limitation des recherches de facteurs premiers sous la racine carrée du nombre. J'ai vu ça en prépa, et ça se démontre somme toute facilement, d'après mes souvenirs

Le plus étonnant, c'est que ma première version, brute force et non limitée, ne semblait pas vouloir converger, alors que celle-ci me donne un temps de recherche de 13 secondes pour un nombre quand même assez grand (suffisamment, en tout cas, pour qu'il y ait au moins 62000 nombres premiers inférieurs à sa racine carrée). Pas mal, je trouve.

Publicités

Une réflexion sur “Plus grand diviseur premier d’un nombre

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s