# Find count of multiples of 3 or 5 in given range in C++

In this tutorial, we are going to learn the basic and efficient code of the given problem that is **Find count of multiples of 3 or 5 in the given range in C++**. Initially, we will know what we have to find. let the range is 1………n and we have to find the count of those number which is either divisible by either 3 or 5.

eg: given range is 1-20 i.e. { 1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,20} , so all the numbers, divisible by 3 or 5 are {3,5,6,9,10,12,15,18,20 } count =9.

Here I’m going to explain two methods to solve this problem.

**Method1 to count the multiples of 3 or 5 in C++**

Use a loop which iterates from 1 – n with the help of condition find it is divisible by 3 or 5 and count all the numbers.

#include<iostream> using namespace std; int main() { int range,i,count; cin>>range; count=0; for(i=1;i<=range;i++) { if(i%3==0||i%5==0) count++; } cout<<count<<endl; return 0; }

Input:

20

Output:

9

Time complexity: **O(n) **

This method works perfectly when the range is less than 10^9 if the range is large than 10^9 this method will give TLE (time limit exceed).

**An alternative method to count the numbers, divisible by 3 or 5 in C++**

We know the count of the number which is divisible by 3 in the given range is equal to the floor(n/3). In the range 1-20 count number divisible by 3 are floor(20/3) = 6 i.e. { 3,6,9,12,15,18}.

Similarly, the count of the number which is divisible by 5 in the given range is equal to the floor(n/5). In the range 1-20 count number divisible by 5 are floor (20/5)=4 i.e.{ 5,10,15,20}.

And count of the number which is divisible by 3 and 5 in the given range is equal to the floor(n/3)+floor(n/5)-floor(n/15)**.** In the range 1-20 count number divisible by 3 are floor(20/3)+floor(20/5) – floor(n/15) =6+4-1=9 i.e. { 3,5,6,9,10,12,15,15,18,20} – {15} = { 3,5,6,9,10,12,15,18,20}.

#include<iostream> using namespace std; int main() { long long int r,i,count; cin>>r; count=r/3; count+=r/5; count-=r/15; cout<<count<<endl; return 0; }

Input:

100

Output:

47

Time complexity: **O(1)**

This method works perfectly when the range is either less than 10^9 or more than 10^9.

Read other tutorials as well,

Nice post on basis of time complexity .

Thanks 🙂