python - My code is inefficent, multiples of 3 and 5 from Project Euler but with a 10 second timeout conditon -

problem statement

this problem programming version of problem 1 projecteuler.net

if list natural numbers below 10 multiples of 3 or 5, 3, 5, 6 , 9. sum of these multiples 23.

find sum of multiples of 3 or 5 below n.

input format

first line contains t denotes number of test cases. followed t lines, each containing integer, n.

output format

for each test case, print integer denotes sum of multiples of 3 or 5 below n.

constraints

1≤t≤105  1≤n≤109 

sample input

2 10 100 

sample output

23 2318 

---

i'm doing first project euler question time constraint challenge. if process takes more 10s autofail.

here sample input:

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

here code:

test_case = int(input()) 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) 

the problem not show me inputs when grading solution going assume 1 of test cases checking until 10^9 take lot more 10 seconds run.

---

previous attempt note: had simpler code ran loop 0 stop_value failed once stop_value got big attempted make while loops (which showed above) skipping in between everything.

---

next attempt:

i tried find maximum multiple of each number , multiples term own factorials wrong output.

to explain thought process on why, considered 10 example, 10//3 = 3. if did 3!*3 [1*3,2*3,3*3] = [3,6,9] multiples of 3 stop_value edit: noticed implemented incorrectly, considering for-loops factorials.

import math  test_case = int(input()) 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) 

your output (stdout)

13 26049952856435659498719093244723189200 

expected output

23 2318 

this generalization of sum of natural numbers. general formula step size of k , maximum number n (with n divisible k) is: 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