Given an integer N, the task is to find the count of numbers from 1 to N which are divisible by all the numbers from 2 to 10.
Examples:
Input: N = 3000
Output: 1
2520 is the only number below 3000 which is divisible by all the numbers from 2 to 10.Input: N = 2000
Output: 0
Approach: Let’s factorize numbers from 2 to 10.
2 = 2
3 = 3
4 = 22
5 = 5
6 = 2 * 3
7 = 7
8 = 23
9 = 32
10 = 2 * 5
If a number is divisible by all the numbers from 2 to 10, its factorization should contain 2 at least in the power of 3, 3 at least in the power of 2, 5 and 7 at least in the power of 1. So it can be written as:
x * 23 * 32 * 5 * 7 i.e. x * 2520.
So any number divisible by 2520 is divisible by all the numbers from 2 to 10. So, the count of such numbers is N / 2520.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of numbers// from 1 to n which are divisible by// all the numbers from 2 to 10int countNumbers(int n){ return (n / 2520);}// Driver codeint main(){ int n = 3000; cout << countNumbers(n); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to return the count of numbers // from 1 to n which are divisible by // all the numbers from 2 to 10 static int countNumbers(int n) { return (n / 2520); } // Driver code public static void main(String args[]){ int n = 3000; System.out.println(countNumbers(n)); } }// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach# Function to return the count of numbers# from 1 to n which are divisible by# all the numbers from 2 to 10def countNumbers(n): return n // 2520# Driver coden = 3000print(countNumbers(n))# This code is contributed# by Shrikant13 |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the count of numbers // from 1 to n which are divisible by // all the numbers from 2 to 10 static int countNumbers(int n) { return (n / 2520); } // Driver code public static void Main(String []args){ int n = 3000; Console.WriteLine(countNumbers(n)); } }// This code is contributed by Arnab Kundu |
PHP
<?php// PHP implementation of the approach// Function to return the count of numbers // from 1 to n which are divisible by // all the numbers from 2 to 10 function countNumbers($n) { return (int)($n / 2520); } // Driver code $n = 3000; echo(countNumbers($n)); // This code is contributed// by Code_Mech.?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the count of numbers // from 1 to n which are divisible by // all the numbers from 2 to 10 function countNumbers(n) { return (n / 2520); } // Driver codevar n = 3000; // Function calldocument.write(Math.round(countNumbers(n))); // This code is contributed by Ankita saini</script> |
1
Time Complexity: O(1), since there is a basic arithmetic operation that takes constant time.
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
