时间戳

首页 > 解决方案 > 项目 euler #1 使用 python 时间复杂度

python - 项目 euler #1 使用 python 时间复杂度

问题描述

欧拉计划的问题 #1内容如下：

如果我们列出所有小于 10 且是 3 或 5 的倍数的自然数，我们会得到 3、5、6 和 9。这些倍数之和是 23。

求 1000 以下所有 3 或 5 的倍数之和。

这是我的尝试：

T = int(input())

for i in range(T):
    sum = 0
    a = int(input())
    for j in range(a):
        if (j%3==0 or j%5==0):
            sum = sum + j

print(sum)

上面的代码提高了时间复杂度，即在某些情况下运行 >10。你可以在这里找到详细信息： 在此处输入图像描述

标签： python

解决方案

您可以计算所有自然数的总和，这些自然数是梯形面积的倍数n并且在下面：m

def sum_multiples(n, m):
    d = (m - 1) // n
    return (1 + d) * d // 2 * n

因此，下面所有 3 或 5 的倍数之和m可以通过计算所有 3 的倍数之和加上所有 5 的倍数之和减去所有15的倍数，3和5的最小公分母：

def sum_3_5(m):
    return sum_multiples(3, m) + sum_multiples(5, m) - sum_multiples(15, m)

所以要回答这个问题，sum_3_5(1000)返回：

233168

推荐阅读