Euler问题#23 (非富足和)的优化解

Question

欧拉项目问题23问：

完全数是指它的适当除数之和与其数完全相等的一个数。例如，28的适当除数之和为1+2+4+7+ 14 = 28，这意味着28是一个完美数。如果一个数n的适当除数之和小于n，则称n为亏，当这个和大于n时称为富足数，由于12是最小的富足数，1+2+3+4+6= 16，则可以写成两个富足数之和的最小数是24。通过数学分析，可以证明所有大于28123的整数都可以写成两个丰富数的和。然而，这个上限不能通过分析进一步降低，即使已知不能表示为两个丰富数之和的最大数小于这个极限。找出所有正整数的和，这些正整数不能写成两个丰富数的和。

我已经尝试优化我的解决方案近一天了，但我的程序还没有准备好变得更小和优化。有人能告诉我怎么做吗？

def isabundant(n): return sum(list(x for x in range(1, int(n/2)+1) if n % x == 0)) > n
abundants = list(x for x in range(1, 28123) if isabundant(x) == True)
sums = 0
for i in range(12, 28123):
    for abundant in abundants:
        if abundant >= i and isabundant(i+abundant) == True: sums += i
print(sums)

Answer 1

你的第一个问题是你想把太多的信息塞到一条线上。因此，您就失去了概述。下面是一个简单的重构：

def is_abundant(n):
    max_divisor = int(n / 2) + 1
    sum = 0
    for x in range(1, max_divisor):
        if n % x == 0:
            sum += x  
    return sum > n

abundants = list(x for x in range(1, 28123) if is_abundant(x))

sums = 0
for i in range(12, 28123):
    for abundant in abundants:
        if abundant >= i and is_abundant(i + abundant):
            sums += i
print(sums)

• == True测试是没有必要的，并被删除。
• 命名改进：isabundant→is_abundant。
• is_abundant中的长语句被分开了。

现在我们可以考虑如何对其进行优化。

一个子问题是计算一个数字的所有除数。我们可以将相关代码放入自己的功能中。我们可以进一步利用这一点，如果是n % i == 0，那么必须有另一个整数k，以便使n == i * k。这意味着我们只需要看更少的数字:只有range(2, 1 + int(sqrt(n)))是有趣的。

def divisors(n):
    """
    Returns all nontrivial divisors of an integer, but makes no guarantees on the order.
    """
    # "1" is always a divisor (at least for our purposes)
    yield 1

    largest = int(math.sqrt(n))

    # special-case square numbers to avoid yielding the same divisor twice
    if largest * largest == n:
        yield largest
    else:
        largest += 1

    # all other divisors
    for i in range(2, largest):
        if n % i == 0:
            yield i
            yield n / i

现在我们可以将我们的is_abundant重写为更简单的了：

def is_abundant(n):
    if n < 12:
        return False
    return sum(divisors(n)) > n

稍后，在主循环中，您正在进行相当奇怪的计算。我们该怎么办？

找出所有正整数的和，这些正整数不能写成两个丰富数的和。

我们还知道，28123以上的所有整数都可以写成这样的和。因此，我们必须看看range(1, 28123 + 1)！我们如何决定一个数字n是否可以写成i和k丰富的数字之和？有任意一个有约束的i，有约束的i < n，还有一个有约束的k < n and n - i == k。这里有一种聪明的方法可以这样写：

def is_abundant_sum(n):
   for i in abundants_smaller_than_n:
       if (n - i) in abundants_smaller_than_n:
           return True
   return False

因为我们不想每次计算abundants_smaller_than_n，所以如果我们比n大的话，我们只需要计算出所有可能的abundants：

def is_abundant_sum(n):
   for i in abundants:
       if i > n:  # assume "abundants" is ordered
         return False
       if (n - i) in abundants:
           return True
   return False

在哪里abundants = [x for x in range(1, 28123 + 1) if is_abundant(x)]。

现在，所要做的就是对这些条件不成立的数字进行求和：

sum_of_non_abundants = sum(x for x in range(1, 28123 + 1) if not is_abundant_sum(x))

我们可以执行一个优化：abundants是一个列表，它是一个有序的数据结构。如果我们搜索列表中没有包含的元素，则必须搜索所有元素。set()数据结构更快，因此：

abundants_set = set(abundants)
def is_abundant_sum(n):
   for i in abundants:
       if i > n:  # assume "abundants" is ordered
         return False
       if (n - i) in abundants_set:
           return True
   return False

Answer 2

一个简单的优化方法是这样做，而不是迭代每一个部门：

def GetSumOfDivs(n):
    i = 2
    upper = n
    total = 1
    while i < upper:
        if n%i == 0:
            upper = n/i
            total += upper
            if upper != i: total += i
        i += 1
    return total

然后，您可以检查返回的值是否大于填充列表的实际数字。

这是这样的:假设你想得到28的除数之和.与其迭代每个数字：+1，+2，+4，+7，+14，它将同时添加2个数字，如: 3，+4+7，+14，因为您一直在减少每个除数的循环上限。

请记住，对于较低的数字，它实际上将需要更多的时间通过，但对于大的数字，你有一个巨大的改进。

时差：(19.381) - (11.419) = 7.962秒，同时生成丰富的列表

另一种优化是在已经生成的丰度列表中搜索，而不是再次检查是否有足够的数量，但是您应该使用字典而不是列表来使搜索速度大大加快。

我对你问题的解决办法：

def GetSumOfDivs(n):
    i = 2
    upper = n
    total = 1
    while i < upper:
        if n%i == 0:
            upper = n/i
            total += upper
            if upper != i: total += i
        i += 1
    return total


def isabundant(n): return GetSumOfDivs(n) > n
lAbundants = [x for x in range(12, 28123) if isabundant(x) == True]
dAbundants = {x:x for x in lAbundants}

sums = 1
for i in range(2, 28123):
    boo = True
    for k in lAbundants:
        if k < i:
            if (i-k) in dAbundants:
                boo = False
                break
        else : break
    if boo == True: sums += i

print(sums)

为什么是一张清单和一本字典？列表是有序的，字典用于快速索引。

总执行时间: 12.08秒

现在试试在C++..。我肯定不到2秒..。XD好运