python - 最接近零的两个产品之间的差异 : non brute-force solution?

Question

在 science museum in Norway 中我遇到了以下数学游戏:

目标是放置从 0 到 9 的 10 位数字，以使两个产品之间的差异最接近于零。 (246是目前最低分)。

回到家我写了下面的暴力代码:

import time
from itertools import permutations


def form_number(x, y, z, a, b):
    # not explicitly stated, but presume that leading zeroes are not allowed
    if x == 0 or a == 0:
        return 0
    return ((100 * x) + (10 * y) + z) * ((10 * a) + b)

def find_nearest_zero(*args):
    assert len(args) == 10
    return form_number(*args[:5]) - form_number(*args[5:])

if __name__ == '__main__':
    start = time.time()
    count = 0
    for p in permutations(range(10), 10):
        result = find_nearest_zero(*p)
        if result == 0:
            count += 1
            print '{}{}{} * {}{} = {n}'.format(*p[:5], n=form_number(*p[:5]))
            print '{}{}{} * {}{} = {n}'.format(*p[5:], n=form_number(*p[5:]))
            print
    print 'found {} solutions'.format(count)
    print time.time() - start

如果我们不允许前导零，那么这将在大约 12 秒内打印出 128 种可能的解决方案。

但我想知道，是否有算法或更好的方法以非暴力方式解决此问题？

Answer 1

如果您假设存在差异为 0 的解决方案，则可以通过质因数来实现。

如果 ab - cd = 0，则 ab 和 cd 的质因数必须相同。您可以通过遍历所有 3 位素数(只有 143 个)开始搜索，并查看它们是否具有仅包含析取数字的倍数。如果是这种情况，您有 2 个三位数号码，只需检查 2 位数号码。

如果您没有找到解决方案，请继续使用 2 位素数并寻找具有不连续数字的 2 位或 3 位倍数。然后你只需要对剩下的2个数字进行排列，这样就少了很多。