我的代码效率低下，是ProjectEuler的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

样本输入

^{pr2}$

样本输出

23
2318

---

我正在做第一个项目欧拉问题，但有一个额外的挑战时间限制。如果处理时间超过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到{}的for循环，一旦{}太大，我试图在所有东西之间跳过while循环（如上所示）。在

---

下一次尝试：

我试着找出每个数的最大倍数，然后用它们自己的阶乘乘以这个项，但是我得到了错误的输出。在

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

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)

您的输出（stdout）

13
26049952856435659498719093244723189200

预期输出

23
2318

Answer 1

虽然我完全同意您应该使用poke所述的自然数之和的公式，但是仍然可以生成所有的数字。有关分析性地解决问题的更多信息，请查看中的this问题数学.SE在

至于所有数字的生成和求和，这是我能迅速想出的最快方法：

n=10**9; sum(xrange(0,n,3)) + sum(xrange(0,n,5)) - sum(xrange(0,n,15))

在i5上执行这一行大约需要5秒，但它消耗了大量内存

Answer 2

这是自然数和的推广。步长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

^{pr2}$