设计最佳算法以找到 '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

但想将其减少到或更好，如果可能。

Answer 1

考虑不是从 1 迭代到 sqrt(n)，而是从 sqrt(n) 向下迭代到 1。第一个找到的除数给出了答案，您不需要进一步进行

Answer 2

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

不幸的是，在最坏的情况下，没有办法在 O(log N) 时间内解决这个问题。事实上，对于任何 p，即使在 O((log N)^p) 时间内也无法做到。很容易证明，如果可能，那么您将能够找到 prime factorization of any number in polynomial time of its size in bytes. No one can do it right now, and there is a widely used RSA cryptosystem, which strongly relies on the fact that no one can factorize numbers so fast. That is one of the reasons everyone is so scared of quantum computers =)

但是，有些算法渐近速度比 O(sqrt(N)) 快。此外，还有一些更快的因式分解启发式算法。我强烈建议阅读有关此事的 wikipedia article。

稍微提高复杂度的方法之一是预先计算所有素数直到 sqrt(N)。然后，如果您尝试仅将 N 除以它们，您将能够找到 N 的质因数分解。了解质数分解后，您可以通过递归搜索有效地遍历所有可能的因数。查找因式分解所花费的时间与检查素数的时间一样多，即 O(sqrt(N) / log(N))。迭代所有除数所花费的时间与这些除数的数量成正比，即 asymptotically less than any polynomial of N.

Answer 3

我花了很多时间寻找这个问题的最佳解决方案，但没有成功。然后我尝试测试@psyco 的方法更好还是@Nyavro 的方法更好。我个人认为从 sqrt(n) to 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 的方法更好，但它们都可以花费几乎相同的时间进行大量输入。

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

Design Optimal Algorithm to find the values of 'a' and 'b'

algorithm

optimization

numbers