python - 获取 O(1) 中总和最小的数的因子

Question

我试图在 O(1) 中找到总和最小的数的因子对。

这里是解释:

If number is 100. Then all the possible pairs are :

1    X  100
2    X  50
4    X  25
5    X  20
10   X  10
20   X  5
25   X  4
50   X  2
100  X  1

这里和最小的一对是 10,10，显然是中间的一对

Similarly if number is 12 then pairs are as follows

1  X  12
2  X  6
3  X  4
4  X  3
6  X  2
12 X  1

此处所需的对是 3,4 或 4,3。

If a number has 'p' pairs then the required one is always ceil(p/2).

如果给定的数字是一个完美的正方形，那么任务就非常简单。这对就是 sqrt(number),sqrt(number).

如果不是，则该对将是 ceil(sqrt(number)),number/ceil(sqrt(number))

<b>given that ceil(sqrt(number)) is a factor of number</b>

或 immediate factor neighbour of sqrt(number):

例如考虑“6”。 6 不是一个完美的正方形。

sqrt(6) 的 ceil 是 3，3 是 6 的因数。所以所需的对是 3,6/3=2

Now consider 102. All pairs are :

1  *  102.0
2  *  51.0
3  *  34.0
6  *  17.0
17  *  6.0
34  *  3.0
51  *  2.0
102 *  1

这里所需的对是 17,6 或 6,17。 Here ceil(sqrt(102)) is 11 . 11 的直接因子邻居是 17 或 6。<b>Now this is what we actually find.</b>

我们如何找到直接因素邻居？

这是我的 O(n) 实现:

import math

l = []
n = int(input())
for i in range(1, n + 1):
    if n % i is 0:
        l.append(i)
middle = l[math.ceil(len(l) / 2)]
print("Required pair is ", middle, ",", n / middle)

Answer 1

这里证明找到对必须至少和整数因式分解一样困难(这意味着没有已知的 O(1) 算法):

如果我们从数字 N 开始并得到总和最小的对，如图所示，除数最接近 sqrt(N)，因此只有 2 种可能性:
1. 该对是 1 - N，这意味着 N 是质数。这是微不足道的情况。
2. 我们找到了一些非平凡的约数 k。这意味着我们可以连续对 k 和 N/k 应用该算法，最终有效地找到所有素因数。