设计最佳算法以找到'a'和'b'的值

Question

假设我们有一个合数（n>3），可以写成：n = a*b，其中a和b是任意整数。

现在，我们的任务是计算a和b的值，使函数f(a,b) = |a-b|最小化。

我已经实现了如下方法。

int n;
cin >> n;      //  Take it from the user

/* Now, find the value of the a and b */
int a = 1;
int b = n;
int temp_a;
int temp_b;

for(temp_a=1; temp_a<=sqrt(n); temp_a++) {
    if(n % temp_a == 0) {
        temp_b = n / temp_a;

        if((temp_b - temp_a) < (b - a)) {
            b = temp_b;
            a = temp_a;
        }
    }
}

print a and b

但希望将其减少到 或更好的情况下，如果可能的话。

- surajs1n

Answer 1

您想找到不大于sqrt(N)的N的最大除数。最简单的方法是迭代所有可能的除数并检查它们。在最坏情况下，它需要O(sqrt(N))的时间。

不幸的是，在最坏情况下，没有办法在O(log N)的时间内解决这个问题。实际上，甚至无法在任何p的时间复杂度为O((log N)^p)。很容易证明，如果可能的话，那么你将能够在字节大小的多项式时间内找到任何数字的质因数分解。目前没有人能做到这一点，而且有一个广泛使用的RSA加密系统，它强烈依赖于没有人能够如此快速地分解数字的事实。这就是为什么每个人都对量子计算机感到如此恐惧的原因之一 =)

然而，有些算法的渐近速度比O(根号N)更快。此外，还有一些更快的启发式因数分解算法。我强烈建议阅读维基百科上的文章了解这方面的知识。

略微提高复杂度的一种方法是预计算所有小于根号N的素数。然后，如果你只尝试用它们来除N，你就能够找到N的质因数分解。知道了质因数分解，你可以通过递归搜索有效地迭代所有可能的整数因子。找到因数分解的时间与正在检查的素数数量成正比，即O(根号N/log(N))。遍历所有因子所花费的时间与这些因子的数量成正比，这个数量是渐近少于任何多项式函数的N。

- stgatilov

Answer 2

我花了很多时间来寻找这个问题的最优解，但是失败了。然后我尝试测试@psyco和@Nyavro的方法哪个更好。我个人认为从sqrt(n)向下计数到1肯定会更好，但为了检查@psyco的观点，我在 Python 程序中实现了两种方法，并绘制了一个图形来比较它们寻找解决方案所需的迭代次数。该图表适用于 4 到 10000 之间的所有合数。以下是我的 Python 实现：

import matplotlib.pyplot as plt
import math
X = 10001
n1 = [0]*X
n2 = []
for i in range(2, int(math.sqrt(X))+1):
    if n1[i] == 0:
        for j in range(i*i, X, i):
            n1[j] = 1

for i in range(4, X):
    if n1[i] == 1:
        n2.append(i)

#print n2
count = []
count2 = []
for n in n2:
    a = 1
    b = n
    c = 0
    flag = 0
    for ta in range(int(math.sqrt(n)), 0, -1):
        c += 1
        if n % ta == 0:
            tb = n / ta
            flag = 1
            if tb-ta <= b-a:
                a = ta
                b = tb
                if flag == 1:
                    break
    count.append(c)
    a = 1
    b = n
    c = 0
    for ta in range(1, int(math.sqrt(n))+1):
        c += 1
        if n % ta == 0:
            tb = n / ta
            if tb-ta <= b-a:
                a = ta
                b = tb

    count2.append(c)

plt.plot(n2, count, 'o')
plt.plot(n2, count2, 'o')
plt.show()

以下是输出图表：

上面的绿色边框是@psyco的代码，而蓝色的边框则是@Nyavro的方法。虽然对于许多输入，它们都可以在几乎相同的时间内完成，但在许多情况下，@Nyavro的方法更好。

- Shubham

---

你是对的。我知道，可以按相反的顺序做。但是，关键案例尚未覆盖。它们仍然需要相同的时间。这就是为什么我问：是否有可能设计一个算法来减少复杂性而不是优化它。 - surajs1n

Answer 3

考虑从sqrt(n)向下迭代，而不是从1到sqrt(n)。第一个找到的因子就是答案，不需要继续进行。

- Nyavro

---

是的，这很好。但是，这不是最优解。我可以给你一个测试用例，在那里你和我的方法将花费相同的时间来执行。 - surajs1n

同意。但不幸的是，我想不出更好的方法来找到除数。 - Nyavro

以 3125 为测试案例，你的方法需要大约30个步骤，而我的则需要大约25个步骤。 - surajs1n