Réduire le nombre de diviseurs d'un nombre entier dans un intervalle

Question

Je suis récemment tombé sur un problème algorithmique et je ne peux pas obtenir la fin de celui-ci. On vous donne un entier positif N < 10^13, et vous devez choisir un entier non négatif M, de sorte que la somme: M N + N (N-1)/2 a le plus petit nombre de diviseurs entre 1 et N, inclusivement. Quelqu'un peut-il me diriger vers la bonne direction pour résoudre ce problème? Merci pour votre temps.

Answer 1

Trouvez un nombre premier P supérieur à N. Il y a un certain nombre de façons de le faire.

Si N est impair, alors M*N + N*(N-1)/2 est un multiple de N. Il doit être divisible par un facteur N, mais si nous choisissons M = P - (N-1)/2, puis M*N + N*(N-1)/2 = P*N, il est donc pas divisible par tout autre entiers compris entre 1 et N Si 0 est pair, M*N + N*(N-1)/2 est un multiple de N/2. Il doit être divisible par n'importe quel facteur de N/2, mais si nous choisissons M = (P - N + 1)/2 (qui doit être un nombre entier), alors M*N + N*(N-1)/2 = (P - N + 1)*N/2 + (N-1)*N/2 = P*N/2, il n'est donc pas divisible par d'autres entiers entre 1 et N.