获取 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).

如果给定的数字是一个完美的正方形，那么这个任务就很好 simple.The 对只是 sqrt(number),sqrt(number).

如果不是那么这对将是 ceil(sqrt(number)),number/ceil(sqrt(number))

<b>假设ceil(sqrt(number))是number的一个因数</b>

或 immediate factor neighbour of sqrt(number):

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

sqrt(6) 的上限是 3，3 是 6.So 的因数，所需的对是 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>这就是我们实际找到的结果。</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(n)，但您可以使用以下程序降低时间复杂度

from math import *

val = floor(sqrt(n))
l2 = []
for i in range(val,n):
    if n%i == 0:
        l2.extend([i,n//i])
        break

print(l2)

这里我们基本上是在计算数字的平方根，并检查它是否是给定输入的因数。我们递增 1，直到找到第一个因子。该因子和所得商的对具有最小的总和。

两个程序的速度比较

from math import *
from time import time

n = 1120304

t0 = time()
l = []
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)

t1 = time()
val = floor(sqrt(n))
l2 = []
for i in range(val,n):
    if n%i == 0:
        l2.extend([i,n//i])
        break

t2 = time()

t1-t0 # 0.1386280059814453
t2-t1 # 0.009765148162841797

Answer 2

我也只能想到一个O(sqrt(n))的方法

from math import sqrt, ceil

m = 200

for i in range(ceil(sqrt(m)), 0, -1):
    if m % i == 0:
        print(i, int(m / i))
        break

我们得到了 10、20

我们知道

(a - b)^2 >= 0

然后我们得到了

a^2 + b^2 >= 2ab

对于我们的案例

x + m/x

我们有

x + m/x >= 2sqrt(m)

所以我们得到了min(sum(x + m/x)的边界，min sum应该是由两个非常接近sqrt(m)的因子产生的；背后的数学问题是x + m/x函数，当x = sqrt(m)时，sum(x + m/x)是最小化的，但是由于我们需要x和m/x都是整数, 所以我们应该尝试找到最接近 sqr(m) 的那些。

Answer 3

我不认为这个问题是一个新问题。我看过一些类似的问题多年以前，但从未见过 O(1) 解决方案。

所以让我们面对现实吧，O(sqrt(n))可能是最好的情况。

Answer 4

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

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

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

Getting factors of a number with least sum in O(1)

python

algorithm

math

mathematical-optimization

data-structures