python - 我的代码效率低下，来自 Project Euler 的 3 和 5 的倍数，但超时条件为 10 秒

Question

问题陈述

This problem is a programming version of Problem 1 from projecteuler.net

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below N.

输入格式

First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.

输出格式

For each test case, print an integer that denotes the sum of all the multiples of 3 or 5 below N.

约束

1≤T≤105 
1≤N≤109

示例输入

2
10
100

示例输出

23
2318

---

我正在做第一个 Project Euler 问题，但有时间限制以应对额外的挑战。如果该过程花费的时间超过 10 秒，它将自动失败。

这是一个示例输入:

2   # number of test cases
10  # first test case
100 # second test case

这是我的代码:

test_case = int(input())
for x in range(0, test_case):       # Loops after every test case
    stop_value = int(input())

    answer = 0

    threes = 0
    while threes < stop_value:      # Checks 3s
        answer += threes
        threes += 3

    fives = 0
    while fives < stop_value:       # Checks 5s
        answer += fives
        fives += 5

    commons = 0
    while commons < stop_value:     # Check 15s
        answer -= commons
        commons += 15

    print(answer)

问题在对我的解决方案进行评分时不会向我显示输入，但我假设其中一个测试用例正在检查直到 10^9，这将花费比运行 10 秒。

---

上一次尝试注意:最初我有一个更简单的代码，它运行一个从 0 到 stop_value 的 for 循环，一旦 stop_value 变得太大了，所以我试图让 while 循环(我在上面展示过)在所有内容之间跳过。

---

下一次尝试:

我试图通过它们自己的阶乘找到每个数字的最大倍数和该术语的倍数，但我得到了错误的输出。

为了解释我的思考过程，我以 10 为例，10//3 = 3。如果我做 3!*3，它将是 [1*3,2*3,3*3 ] = [3,6,9] 是 stop_value 的所有 3 的倍数 编辑:我注意到这个实现不正确，我目前正在考虑阶乘的 for 循环。

import math

test_case = int(input())
for x in range(0, test_case):       # Loops after every test case
    stop_value = int(input())

    threes = stop_value // 3
    fives = stop_value // 5
    commons = stop_value // 15

    answer = math.factorial(threes)*3 + math.factorial(fives)*5 - math.factorial(commons)*15

    print(answer)

您的输出(标准输出)

13
26049952856435659498719093244723189200

预期输出

23
2318

Answer 1

这是自然数之和的推广。步长 k 和最大数 n(n 可被 k 整除)的一般公式为: n/k/2 * (n + k)。

def euler1 (n):
    max3 = range(0, n, 3)[-1]
    max5 = range(0, n, 5)[-1]
    max15 = range(0, n, 15)[-1]

    sum3 = (max3 + 3) * max3 // 3 // 2
    sum5 = (max5 + 5) * max5 // 5 // 2
    sum15 = (max15 + 15) * max15 // 15 // 2

    return sum3 + sum5 - sum15

>>> euler1(10)
23
>>> euler1(100)
2318
>>> euler1(10**100)
23333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666668