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))