1655. Наименьшее общее кратное

 

Найти наименьшее общее кратное всех целых чисел от 1 до n.

Наименьшим общим кратным натуральных чисел a1, a2, ..., ak называется число A, такое что A делится на ai для всех i от 1 до k, причем A – наименьшее натуральное число, обладающее таким свойством.

 

Вход. Одно целое число n (1 ≤ n ≤ 1000).

 

Выход. Выведите одно целое число – наименьшее общее кратное всех чисел от 1 до n.

 

Пример входа

Пример выхода

3

6

 

 

РЕШЕНИЕ

НОК

 

Анализ алгоритма

Поскольку n ≤ 1000, то следует воспользоваться длинной арифметикой. Например, классом BigInteger в Java. Напомним, что НОК(a, b) = a * b / НОД(a, b).

 

Реализация алгоритма

 

import java.util.*;

import java.math.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    BigInteger res = BigInteger.ONE;

    for(int i = 1; i <= n; i++)

    {

      BigInteger x = BigInteger.valueOf(i);

      res = res.multiply(x).divide(res.gcd(x));

            // res = res * x / gcd(res,x)

    }

    System.out.println(res);

    con.close();

  }

}