Project Euler #1: Multiples of 3 and 5

Problem Statement (original problem)

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$N$.

Input Format

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

Output Format

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

Constraints 

1≤T≤105

  1≤N≤109
10≤N≤4×1016

 

ANSWER :  

Obviously first everyone would go with the brute-force method which gives 2 incorrect test cases, following is the brute-force code I coded in c++ and python.

C++:

Python:

But you don't need iteration at all for this problem.

Consider; the sum of all numbers from 1 to n is equal to n*(n+1)/2. Also the sum of all numbers less than n that divides d equals d times the sum of all numbers less than n/d.

So the sum of all numbers less than 1000 that divides 3 is

3*floor(999/3)*(floor(999/3)+1)/2

Likewise the sum of all numbers less than 1000 that divides 5 is

5*floor(999/5)*(floor(999/5)+1)/2

Adding the two numbers would over count though. Since the numbers that divides both 3 and 5 would get counted twice. The numbers that divides both 3 and 5 is precisely the numbers that divides 3*5/gcd(3,5)=15/1=15.

The sum of all numbers less than 1000 that divides 15 is

15*floor(999/15)*(floor(999/15)+1)/2

So the final result is that the sum of all numbers less than 1000 that divides either 3 or 5 equals:

  3 * (floor(999/3)  *  (floor(999/3)+1))/2
+ 5 * (floor(999/5)  *  (floor(999/5)+1))/2
-15 * (floor(999/15) * (floor(999/15)+1))/2

so  we get the  final working code which gives complete marks as below :

in python: 

Hope all your questions about this problem is answered here. Be back soon with the project Eular #2 :)

All project Eular problems can be found at : https://projecteuler.net/archives

 

sdcxvzd vmnldbgdfbdfjb

dsfxvxvxc