JavaScript Program to Find Smallest Number that is Divisible by First n Numbers
Given a number, our task is to find the smallest number that is evenly divisible by the first n numbers without giving any remainder in JavaScript.
Example:
Input: 10
Output: 2520
Explanation:
2520 is smallest number which is completely divisible by numbers from 1 to 10.
Below are the following approaches for finding the Smallest number that is divisible by the first n numbers:
Table of Content
- Brute Force Approach
- Using LCM (Lowest Common Multiple)
Brute Force Approach
To Find the smallest number divisible by the first n numbers using Brute Force Approach first initialize num with n. Use a while loop to find the smallest divisible number. In the loop, set divisible to true, and iterate from 1 to n, checking if num is divisible by i. If not, set divisible to false and break. If divisible remains true, return num. Otherwise, increment num and continue.
Example: Demonstration of Finding the Smallest number divisible by the first n numbers using the Brute Force Approach.
function smallDivi(n) {
let num = n;
while (true) {
let divisible = true;
for (let i = 1; i <= n; i++) {
if (num % i !== 0) {
divisible = false;
break;
}
}
if (divisible) {
return num;
}
num++;
}
}
console.log(smallDivi(10));
Output
2520
Time Complexity: O(num * n)
Space Complexity: O(1)
Using LCM (Lowest Common Multiple)
In this approach, first implement gcd to find the greatest common divisor using Euclid’s algorithm. Implement lcm to calculate the least common multiple as a * b / gcd(a, b). Initialize the answer to 1 and iterate from 2 to n, updating the answer with the least common multiple of the answer and i. After the loop, the answer holds the smallest number divisible by the first n numbers. Return answer.
Example: Demonstration of Finding the the Smallest number that is divisible by first n numbers using LCM (Lowest Common Multiple).
function smallestDivisibleLCM(n) {
function calculateGCD(a, b) {
return b === 0 ? a : calculateGCD(b, a % b);
}
function calculateLCM(a, b) {
return (a * b) / calculateGCD(a, b);
}
// Initialize the result to 1
let answer = 1;
// Iterate through numbers from 2 to n to calculate LCM
for (let i = 2; i <= n; i++) {
answer = calculateLCM(answer, i);
}
return answer;
}
console.log(smallestDivisibleLCM(10));
Output
2520
Time Complexity: O(n * log(n)).
Space Complexity: O(1).