Smallest multiple

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Ans:-232792560

Code

import fractions
def compute():
ans = 1
for i in range(1, 21):
ans *= i // fractions.gcd(i, ans)
return str(ans)

print(compute())

Programming problem from Hackerrank.com

2520 is the smallest number that can be divided by each of the numbers from 1 to 10  without any remainder.
What is the smallest positive number that is evenly divisible(divisible with no remainder) by all of the numbers from 1 to N ?

Input Format

First line contains T that denotes the number of test cases. This is followed by  T lines, each containing an integer, N .

Constraints

• 1⩽T⩽10
• 1⩽N⩽40

Output Format

Print the required answer for each test case.

Sample Input

2
3
10

Sample Output

6
2520

Explanation

• You can check 6 is divisible by each of {1,2,3} , giving quotient of  {6,3,2} respectively.
• You can check 2520 is divisible by each of {1,2,3,4,5,6,7,8,9,10} giving quotient of {2520,1260,840,630,504,420,360,315,280,252}  respectively.

Solution:-

• The smallest number n that is evenly divisible by every number in a set {k1, k2, …, k_m}
is also known as the lowest common multiple (LCM) of the set of numbers.
• The LCM of two natural numbers x and y is given by LCM(x, y) = x * y / GCD(x, y).
• When LCM is applied to a collection of numbers, it is commutative, associative, and idempotent.
•  Hence LCM(k1, k2, …, k_m) = LCM(…(LCM(LCM(k1, k2), k3)…), k_m).

Code:-

import math
def compute(n):
ans = 1
for i in range(1, n+1):
ans *=i// math.gcd(i, ans)
return str(ans)

t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
print(compute(n))