Programs that Find Numbers Divisible by 5 or 3

Question

i want to make a program to find how many number is divisible by 3 or 5 in a number for example 10 has 3 9 6 divisible by 3 and has 5 and 10 divisible by 5 so total is 5 and so on so i write my code

import math
n=float(raw_input())
div3=(n-2)/3
div5=(n-4)/5
f1=math.ceil(div3)
f2=math.ceil(div5)
sumss=f1+f2
print int(sumss)

but in some number it get wrong answer and the range of input number will be from 1 to 10^18 so i need to use math in it because the time limit for the problem test is 2 second any one have any efficiently equation to make that the loop cant make it it take very long time

Answer 1

This is probably a project Euler question. The issue is that some numbers can be shared by 3 and 5. For instance 22:

divisors of 3: 3 6, 9, 12, 15, 18, 21.

divisors of 5: 5 10, 15, 20

For both 15 occurs, so you did a double count.

The advantage is that 3 and 5 are relatively prime, so the only numbers that are shared are the ones dividable by 15. So you simply need to undo the double counting:

n=int(raw_input())
div3=n//3
div5=n//5
div15=n//15
sumss=div3+div5-div15
print sumss

In case you allow double counting (15 should be counted twice), you can simply use:

n=int(raw_input())
div3=n//3
div5=n//5
sumss=div3+div5
print sumss

Note that the programs omitted the floating point arithmetic: this will result in both faster and more precise programs since floating point numbers work with a limited mantisse and thus can fail to represent a large number correctly (resulting by small errors). Furthermore in general integer arithmetic is faster.

Project Euler #1

Now the problem statement of Project Euler is a bit different: it asks to sum up these numbers. In order to do that, you have to construct an expression to sum up the first k multiples of l:

 k
---
\
/     l*i
---
i=1

Using Wolfram Alpha, one gets this expression. So you can calculate these as:

def suml (k,l) :
    return k*(k+1)*l/2

n=int(raw_input())
div3=n//3
div5=n//5
div15=n//15
sumss=suml(div3,3)+suml(div5,5)-suml(div15,15)
print sumss

This program gives 119 for n=22 which - you can verify above - is correct if you count 15 only once.