logo标签列表

欧拉计划第23题 - Python非丰和数之和

pythonalgorithmmath
3
我一直在处理“欧拉计划＃23”。
这是任务：
问题23 完全数是其真因数之和正好等于该数的数字。例如，28的真因数之和为1 + 2 + 4 + 7 + 14 = 28，这意味着28是一个完全数。 如果数字n的真因数之和小于n，则称数字n为不足数，如果此总和超过n，则称其为丰富数。 由于12是最小的丰富数，因此可以写成两个丰富数之和的最小数字为24（1 + 2 + 3 + 4 + 6 = 16）。通过数学分析，可以证明大于28123的所有整数都可以写成两个丰富数的和。但是，即使已知不能将不能表示为两个丰富数之和的最大数字小于此限制，但此上限也无法通过分析进一步降低。 找到所有不能写成两个丰富数之和的正整数的总和。
这是我的代码：
import math

def getDivisors(num):
    n = math.ceil(math.sqrt(num))
    total = 1
    divisor = 2
    while (divisor < n):
        if (num%divisor == 0):
            total += divisor
            total += num//divisor
        divisor+=1
    return total

def isAbundant(num):
    if (getDivisors(num) > num):
        return True
    else:
        return False

abundentNums = []
for x in range (0,28124):
    if (isAbundant(x)):
        abundentNums.append(x)
del abundentNums[0]

sums = [0]*28124
for x in range (0, len(abundentNums)):
    for y in range (x, len(abundentNums)):
            sumOf2AbundantNums = abundentNums[x]+abundentNums[y]
            if (sumOf2AbundantNums<= 28123):
                if (sums[sumOf2AbundantNums] == 0):
                    sums[sumOf2AbundantNums] = sumOf2AbundantNums

total = 0
for x in range (1,len(sums)):
    if (sums[x] == 0):
        total +=x

print('\n', total)

我得到的总值是4190404。正确答案是4179871。我花了一个小时查看我的代码，但我无法找到错误。我应该改变什么来纠正这个错误？我的答案很接近。提前致谢。

PS. 我是Python的新手。运行时间为25秒，任何优化都将非常有用。

这是为 Hackerrank 比赛吗？ - Anthony Collins
@AnthonyCollins 项目欧拉是一个数学/谜题问题网站。 - MooingRawr
3
不，PE 只是为了娱乐和消磨时间。 - Varun Narayanan
1
你应该能够在这里包含一些动态规划方法（或缓存递归）。例如，如果已知28的因数，则可以将该知识用于56、84等。这将为您节省大量时间。 - user2390182
哦，好的。我的错。我读到这个时想到了一个名为“ProjectEuler+” 的当前 HR 竞赛，不确定这是否相关。继续哈哈。 - Anthony Collins
显示剩余6条评论
5个回答
7

你的 getDivisors 函数有误，它没有统计平方数的根因子（例如，如果 num=25，它会返回 1）。这是一个更正后的版本：

def getDivisors(num):
    if num==1:
        return 1
    n = math.ceil(math.sqrt(num))
    total = 1
    divisor = 2
    while (divisor < n):
        if (num%divisor == 0):
            total += divisor
            total += num//divisor
        divisor+=1
    if n**2==num:
        total+=n
    return total

使用这个函数，我得到了所需的结果4179871。
divisor <= math.floor(math.sqrt(num)) 和 divisor < math.ceil(math.sqrt(num)) 不是相同的吗？ - Varun Narayanan
@Varun Narayanan 注意，我已编辑了我的答案（仅对代码进行了最小更改）。 - Miriam Farber
1
关于“除数是否小于等于math.floor(math.sqrt(num))与除数是否小于math.ceil(math.sqrt(num))不是一样的吗？”这个问题，实际上它们并不相同。例如，如果num=25，则floor和ceil都会得到5，因此<和<=之间存在差异。 - Miriam Farber
谢谢， if (n**2 == num): total -= n 和设置 n = math.ceil(math.sqrt(num)) 就解决了 :) - Varun Narayanan
1

我对上述代码进行了一些更改，然后在13秒内得到了正确的答案。我的CPU是英特尔酷睿i5。以下是我的代码：

from array import array
import math


def find_abundant(number):
    sum_factor = 1
    value = math.ceil(math.sqrt(number))
    if number == 1:
        return False
    for i in range(2, value):
        if number % i == 0:
            sum_factor += (i+(number//i))
    if value**2 == number:
        sum_factor += value
    if sum_factor > number:
        return True
    else:
        return False


numbers = [0]*28123
abundant_numbers = array("i", [])
for abundant in range(1, 28124):
    if find_abundant(abundant):
        abundant_numbers.append(abundant)

for x in abundant_numbers:
    for y in abundant_numbers[0:abundant_numbers.index(x)+1]:
        z = x+y
        if z < 28124 and numbers[z-1] == 0:
            numbers[z-1] = z


_sum = 0
for vary in range(1, len(numbers)+1):
    if numbers[vary-1] == 0:
        _sum += vary
print(_sum)}
1

这段代码在我的电脑上运行了6秒钟：

from math import sqrt
import itertools
import functools
import operator
#simplicity test
def fuc(a):
    d = 1
    z = 0
    while d<= sqrt(a):
        d = d + 1
        if a == 2:
            z = a
        elif (a%d) == 0:
            z = False
            break

        else:
            z = a
    return z
#prime number divisors
def func(value):
    v = []
    d = 1
    value1= value# for optimization
    while d <= sqrt(value1):
        d+=1
        if fuc(d)!= False and value1 % d == 0:
            v.append(d)
            value1 = value1/d
            d = 1
    if value1 != value and value1 != 1:
        v.append(value1)
    return v
# all number divisors without 1 and source number
def calculate_devisors(n):
    prime_multiples_list = func(n)
    unique_combinations = set()
    for i in range(1, len(prime_multiples_list)):
        unique_combinations.update(set(itertools.combinations(prime_multiples_list,i)))
        combinations_product = list(functools.reduce(operator.mul,i) for i in unique_combinations)
        combinations_product.sort()
    try:
        return combinations_product
    except:
        return []

abundentNums = []

for n in range(1,28123):
    if sum(calculate_devisors(n))+1>n:
        abundentNums.append(n)

sums = [0]*28124
for x in range (0, len(abundentNums)):
    for y in range (x, len(abundentNums)):
        sumOf2AbundantNums = abundentNums[x]+abundentNums[y]
        if (sumOf2AbundantNums<= 28123):
            if (sums[sumOf2AbundantNums] == 0):
                sums[sumOf2AbundantNums] = sumOf2AbundantNums
ans = 0
for i in range(1,len(sums)):
    if sums[i]==0:
        ans+=i
print(ans)
0

使用numpy的一种可能的解决方案，避免了嵌套循环，并且在我的笔记本电脑上通常少于3秒钟，如下所示。

描述

将您的过剩数字列表转换为numpy数组A。创建一个包含问题中限制范围内的1到数字的额外数组B。使用外部求和创建包含所有可能的过剩数字组合的矩阵。删除重复条目。最后，在C中表示为两个过剩数字之和的所有数字的总和与B中所有数字的总和之间的差是所寻找的数量。

代码

A = np.array(abundentNums)
B = np.linspace(1,28123,28123)
C = np.unique(np.add.outer(A, A)[(np.add.outer(A, A) < 28124)])
ans = int(np.sum(B) - np.sum(C))

因此，包括由Miriam Farber更正的getDivisors函数在内的整个代码为：
import math
import numpy as np

def getDivisors(num):
    if num==1:
        return 1
    n = math.ceil(math.sqrt(num))
    total = 1
    divisor = 2
    while (divisor < n):
        if (num%divisor == 0):
            total += divisor
            total += num//divisor
        divisor+=1
    if n**2==num:
        total+=n
    return total

def isAbundant(num):
    if (getDivisors(num) > num):
        return True
    else:
        return False

abundentNums = []
for x in range (0,28124):
    if (isAbundant(x)):
        abundentNums.append(x)
del abundentNums[0]


A = np.array(abundentNums)
B = np.linspace(1,28123,28123)
C = np.unique(np.add.outer(A, A)[(np.add.outer(A, A) < 28124)])
ans = int(np.sum(B) - np.sum(C))

进一步的速度优化可能是使用列表解析来生成丰富数字的列表。
0

我发现这些小调整可能有助于减少总共所需的时间。在我的电脑上，我用了大约4秒钟。

from math import sqrt
from itertools import compress
start = time.process_time()

abundant_nos = []
for i in range(12,28123):
    factor = 0
    for j in range(2,int(sqrt(i))+1):
        if i%j == 0:
            factor+= j + i//j
            if j == sqrt(i):
                factor -= j
    if factor>i:
        abundant_nos.append(i)
num_list = [True]*28123
k = 0
for i in abundant_nos:
    for j in abundant_nos[k:]:
        if(i+j>28123): break
        num_list[i+j-1] = False
    k+=1
answer = sum(compress(range(1,28124),num_list))

print(answer)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接