using loop bring smallest prime number divisble by 1
Answers
Answer:
Given a number n find the smallest number evenly divisible by each number 1 to n.
Examples:
Input : n = 4
Output : 12
Explanation : 12 is the smallest numbers divisible
by all numbers from 1 to 4
Input : n = 10
Output : 2520
Input : n = 20
Output : 232792560
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
If you observe carefully the ans must be the LCM of the numbers 1 to n.
To find LCM of numbers from 1 to n –
Initialize ans = 1.
Iterate over all the numbers from i = 1 to i = n.
At the i’th iteration ans = LCM(1, 2, …….., i). This can be done easily as LCM(1, 2, …., i) = LCM(ans, i).
Thus at i’th iteration we just have to do –
ans = LCM(ans, i)
= ans * i / gcd(ans, i) [Using the below property,
a*b = gcd(a,b) * lcm(a,b)]
Note : In C++ code, the answer quickly exceeds the integer limit, even the long long limit.
Explanation:
Answer:
Given a number n find the smallest number evenly divisible by each number 1 to n.
Examples:
Input : n = 4
Output : 12
Explanation : 12 is the smallest numbers divisible
by all numbers from 1 to 4
Input : n = 10
Output : 2520
Input : n = 20
Output : 232792560