Minimiere Anzahl der Teiler einer ganzen Zahl innerhalb eines Intervalls

Question

Ich bin kürzlich auf ein algorithmisches Problem gestoßen und ich kann das Ende davon nicht erreichen. Sie erhalten eine positive ganze Zahl N < 10^13, und Sie müssen eine nichtnegative ganze Zahl M so wählen, dass die Summe: M N + N (N-1)/2 die kleinste Anzahl von Teilern hat, die dazwischen liegen 1 und N, inklusive. Kann mir jemand die richtige Richtung zeigen, um dieses Problem zu lösen? Vielen Dank für Ihre Zeit.

Answer 1

Suchen Sie eine Primzahl P größer als N. Es gibt eine Reihe von Möglichkeiten, dies zu tun.

Wenn N ungerade ist, dann ist M*N + N*(N-1)/2 ein Vielfaches von N. Es wird von jedem Faktor N teilbar sein muss, aber wenn wir wählen M = P - (N-1)/2, dann M*N + N*(N-1)/2 = P*N, so dass es nicht teilbar durch andere ganze Zahlen zwischen 1 und N ist .

Wenn N gerade ist, dann ist M*N + N*(N-1)/2 ein Vielfaches von N/2. Es muss durch irgendeinen Faktor von N/2 teilbar sein, aber wenn wir M = (P - N + 1)/2 wählen (was eine ganze Zahl sein muss), dann M*N + N*(N-1)/2 = (P - N + 1)*N/2 + (N-1)*N/2 = P*N/2, so ist es nicht teilbar durch andere ganze Zahlen zwischen 1 und N.