Read the problem statement here:
Project Euler: https://projecteuler.net/problem=5
HackerRank: https://www.hackerrank.com/contests/projecteuler/challenges/euler005/problem
We need to find the Least Common Multiple (LCM) of all the numbers from 1 to N so as to find the smallest positive number that can be evenly divided by all the N numbers.
We first have to calculate Greatest Common Divisor (GCD) or Highest Common Factor (HCF) to calculate the LCM of all the numbers.
What is GCD? #
If we find all the prime factors of each of the numbers then multiplying the common factors gives us the GCD.
12 = 2 * 2 * 3 24 = 2 * 2 * 2 * 3 48 = 2 * 2 * 2 * 2 *3 GCD = Multiplication of common prime factors GCD(12, 24, 48) = 2 * 2 * 3 = 12
There is another way of expressing it:
Listing all the factors 12 = 1, 2, 3, 4, 6, 12 24 = 1, 2, 3, 4, 6, 8, 12, 24 48 = 1, 2, 3, 4, 6, 8, 12, 16, 24, 48 GCD = Pick the greatest common factor GCD(12, 24, 48) = 12
What is LCM? #
It is the smallest positive number that is the multiple of two or more numbers.
Multiples of 30 = 30, 60, 90, 120, … Multiples of 45 = 45, 90, 135, 180, … Multiples of 15 = 15, 30, 45, 60, 75, 90, 105, … LCM = Least Common Multiple LCM(30, 45, 15) = 90
How to compute LCM? #
\[LCM(a, b) = \dfrac{a * b}{GCD(a, b)}\]
The above relation only holds true for two numbers.
\[LCM(a, b, c) \neq \dfrac{a * b * c}{GCD(a, b, c)}\]
To solve this problem we need to find the LCM of N numbers. Therefore, to find the LCM of more than two numbers we need an array consisting of the numbers. But, in this case, we can do that by initializing result = 1 and then start traversing from i=2 to i=n. For each iteration we calculate, result = LCM(result, i) = (result * i) / gcd(result, i).
Java code:
import java.util.*; class Solution{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t– > 0){ int n = in.nextInt(); System.out.println(findLCM(n)); } in.close(); } static long findLCM(int n){ long result = 1; for(int i=2; i<=n; i++){ result = (result * i) / findGCD(result, i); } return result; } static long findGCD(long a, long b){ //Finding GCD using Euclid’s Algorithm if(b == 0){ return a; } return findGCD(b, a % b); } }
The time complexity of this code is \(O(n)\).
References: