获得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))

given that ceil(sqrt(number)) is a factor of number

或在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.Now this is what we actually find.

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

这是我的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 应用该算法，最终有效地找到所有素因数。