为什么我的项目欧拉问题1代码返回的答案是232169而不是233169（当我输入1000时）？

Question

这一切都是用Python编写的，我知道它不是很好，也不是很高效，但我仍在学习。任何有关主题标题和任何效率提升的帮助将不胜感激！

# Problem 1 - find all the multiples of 5 and 3 between 0 and a number (including the number).
import math

print("This programme finds all the multiples of 5 and 3 between 0 and a number (including the number) and also finds "
      "the sum.")

number = int(input("Input a natural number: "))
amount_of_threes = math.floor(number / 3) + 1
# The +1 is due to the 'stop' value not being included in a for loop (for i in range(start, stop))
multiples = []


for i in range(1, amount_of_threes):
    multiples.append(i * 3)

amount_of_fives = math.floor(number/5) + 1

for i in range(1, amount_of_fives):
    multiples.append(i*5)

# must get rid of duplicates such as 15 which is a common multiple
unique_multiples = []
for item in multiples:
    if item not in unique_multiples:
        unique_multiples.append(item)

unique_multiples.sort()

print(f"These are all the multiples of 5 and 3 below {number}: {unique_multiples}")

total = 0
for item in unique_multiples:
    total += item

print(f"{total} is the total of the multiples.")

我尝试将 1000 分配给变量“number”，得到 232169，应该得到 233169。相差 1000。

Answer 1

说，欢迎来到堆栈溢出。

考虑到你说“我还在学习”python，我想回答你的问题。希望我的回答对你有用。

在你的算法中，你基本上采取以下步骤：

• 计算该范围内有多少个 3 的倍数（提示）。
• 用这些倍数创建一个列表。
• 计算有多少个5的倍数。
• 将这些倍数添加到列表中。
• 创建唯一倍数列表。
• 迭代此倍数列表以验证它不在唯一的倍数列表中。
• 对唯一倍数列表进行排序。
• 获取列表中唯一倍数的总和。

一些评论：

1. 当您有一个数字列表时，您无需对其进行排序即可获得总数。

2. 您可以使用函数

   sum

   来获取数字列表的总和。它也在列表上进行迭代，但它是一个更优雅的代码。

3. 在任何给定的问题中，尝试迭代最少的次数：如果可能，只迭代一次。

4. 该算法的复杂度为N^2

考虑这段代码（仅迭代一次，同时检查条件）：

N = 1000

total = 0
for n in range(1, N):
    if n%3==0 or n%5==0:
        total += n

print(total)

或者简单地利用Python丰富的表现力：

print(sum(n for n in range(1, N) if not (n%3 and n%5)))

此代码的复杂度为 N，在某些情况下仍然可能令人望而却步（尝试解决 N = 1e12）。

另一种不使用暴力的解决方案可能是这样的：

• 计算范围内有多少个 3、5 和 3*5 的倍数（您在第一步中已经得到了这个提示）
• 计算之前每个倍数的从 1 到 n 的数字之和
• 将每个总和乘以相关倍数

下面的代码以恒定的复杂性解决了这个问题：

N = 1000

sumto = lambda    n:  n*(n+1) // 2 # 1+2+3+4+...+n
mults = lambda m, n: (n-1) // m    # number of multiples of m below n

print(3*sumto(mults(3,N)) + 5*sumto(mults(5,N)) - 15*sumto(mults(15,N)))