最小化区间内整数的约数
Minimize number of divisors of an integer within an interval
我最近偶然发现了一个算法问题，我无法解决它。给定一个正整数 N < 10^13，你需要选择一个非负整数 M，使得和：MN + N(N-1) / 2 有介于 1 和 N（含）之间的最少除数。
有人能指出我解决这个问题的正确方向吗？
谢谢你的时间。
找到一个大于 N 的素数 P。有很多方法可以做到这一点。
如果N是奇数，那么M*N + N*(N-1)/2是N的倍数，必须能被N的任意一个因子整除，但是如果我们选择M = P - (N-1)/2，那么M*N + N*(N-1)/2 = P*N，所以它不能被 1 到 N 之间的任何其他整数整除。
如果 N 是偶数，则 M*N + N*(N-1)/2 是 N/2 的倍数。它必须能被 N/2 的任何因数整除，但如果我们选择 M = (P - N + 1)/2（必须是整数），则 M*N + N*(N-1)/2 = (P - N + 1)*N/2 + (N-1)*N/2 = P*N/2，因此它不能被 1 之间的任何其他整数整除和 N.
我最近偶然发现了一个算法问题，我无法解决它。给定一个正整数 N < 10^13，你需要选择一个非负整数 M，使得和：MN + N(N-1) / 2 有介于 1 和 N（含）之间的最少除数。 有人能指出我解决这个问题的正确方向吗？ 谢谢你的时间。
找到一个大于 N 的素数 P。有很多方法可以做到这一点。
如果N是奇数，那么M*N + N*(N-1)/2是N的倍数，必须能被N的任意一个因子整除，但是如果我们选择M = P - (N-1)/2，那么M*N + N*(N-1)/2 = P*N，所以它不能被 1 到 N 之间的任何其他整数整除。
如果 N 是偶数，则 M*N + N*(N-1)/2 是 N/2 的倍数。它必须能被 N/2 的任何因数整除，但如果我们选择 M = (P - N + 1)/2（必须是整数），则 M*N + N*(N-1)/2 = (P - N + 1)*N/2 + (N-1)*N/2 = P*N/2，因此它不能被 1 之间的任何其他整数整除和 N.