# Smallest number divisible by first n numbers

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

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

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.

Below is the implementation of the logic.

## C++

`// C++ program to find smallest number evenly divisible by` `// all numbers 1 to n` `#include<bits/stdc++.h>` `using` `namespace` `std;` `// Function returns the lcm of first n numbers` `long` `long` `lcm(` `long` `long` `n)` `{` ` ` `long` `long` `ans = 1; ` ` ` `for` `(` `long` `long` `i = 1; i <= n; i++)` ` ` `ans = (ans * i)/(__gcd(ans, i));` ` ` `return` `ans;` `}` `// Driver program to test the above function` `int` `main()` `{` ` ` `long` `long` `n = 20;` ` ` `cout << lcm(n);` ` ` `return` `0;` `}` |

## Java

`// Java program to find the smallest number evenly divisible by` `// all numbers 1 to n` ` ` `class` `GFG{` `static` `long` `gcd(` `long` `a, ` `long` `b)` `{` ` ` `if` `(a%b != ` `0` `)` ` ` `return` `gcd(b,a%b);` ` ` `else` ` ` `return` `b;` `}` `// Function returns the lcm of first n numbers` `static` `long` `lcm(` `long` `n)` `{` ` ` `long` `ans = ` `1` `; ` ` ` `for` `(` `long` `i = ` `1` `; i <= n; i++)` ` ` `ans = (ans * i)/(gcd(ans, i));` ` ` `return` `ans;` `}` ` ` `// Driver program to test the above function` `public` `static` `void` `main(String []args)` `{` ` ` `long` `n = ` `20` `;` ` ` `System.out.println(lcm(n));` `}` `}` |

## C#

`// C# program to find smallest number` `// evenly divisible by` `// all numbers 1 to n` `using` `System;` `public` `class` `GFG{` ` ` `static` `long` `gcd(` `long` `a, ` `long` `b)` `{` `if` `(a%b != 0)` ` ` `return` `gcd(b,a%b);` `else` ` ` `return` `b;` `}` `// Function returns the lcm of first n numbers` `static` `long` `lcm(` `long` `n)` `{` ` ` `long` `ans = 1; ` ` ` `for` `(` `long` `i = 1; i <= n; i++)` ` ` `ans = (ans * i)/(gcd(ans, i));` ` ` `return` `ans;` `}` `// Driver program to test the above function` ` ` `static` `public` `void` `Main (){` ` ` `long` `n = 20;` ` ` `Console.WriteLine(lcm(n));` ` ` `}` `//This code is contributed by akt_mit ` `}` |

## Python3

`# Python program to find the smallest number evenly ` `# divisible by all number 1 to n` `import` `math` ` ` `# Returns the lcm of first n numbers` `def` `lcm(n):` ` ` `ans ` `=` `1` ` ` `for` `i ` `in` `range` `(` `1` `, n ` `+` `1` `):` ` ` `ans ` `=` `int` `((ans ` `*` `i)` `/` `math.gcd(ans, i)) ` ` ` `return` `ans` ` ` `# main` `n ` `=` `20` `print` `(lcm(n))` |

## PHP

`<?php` `// Note: This code is not working on GFG-IDE` `// because gmp libraries are not supported` `// PHP program to find smallest number` `// evenly divisible by all numbers 1 to n` `// Function returns the lcm` `// of first n numbers` `function` `lcm(` `$n` `)` `{` ` ` `$ans` `= 1;` ` ` `for` `(` `$i` `= 1; ` `$i` `<= ` `$n` `; ` `$i` `++)` ` ` `$ans` `= (` `$ans` `* ` `$i` `) / (gmp_gcd(` `strval` `(ans),` ` ` `strval` `(i)));` ` ` `return` `$ans` `;` `}` `// Driver Code` `$n` `= 20;` `echo` `lcm(` `$n` `);` `// This code is contributed by mits` `?>` |

## Javascript

`<script>` `// Javascript program to find the smallest number evenly divisible by` `// all numbers 1 to n` `function` `gcd(a, b)` `{` ` ` `if` `(a%b != 0)` ` ` `return` `gcd(b,a%b);` ` ` `else` ` ` `return` `b;` `}` ` ` `// Function returns the lcm of first n numbers` `function` `lcm(n)` `{` ` ` `let ans = 1; ` ` ` `for` `(let i = 1; i <= n; i++)` ` ` `ans = (ans * i)/(gcd(ans, i));` ` ` `return` `ans;` `}` ` ` `// function call` ` ` ` ` `let n = 20;` ` ` `document.write(lcm(n));` ` ` `</script>` |

**Output :**

232792560

The above solution works fine for a single input. But if we have multiple inputs, it is a good idea to use Sieve of Eratosthenes to store all prime factors. Please refer below article for Sieve based approach.

LCM of First n Natural Numbers

This article is contributed by **Ayush Khanduri**. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.