Algoholic.in.ua

Решения > НОК

НОК JavaС++

Категория: Решения | Добавлено: 2015-09-14 | Просмотров: 418

Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка.

Алгоритм:

  1. Находим НОД заданных чисел.
  2. Делим произведение данных чисел на НОД.

Код реализации на Java:

        import java.io.*;
        import java.util.*;
        static int gcd(int a,int b){
            //1
	    while (b != 0) {
                int tmp = a % b;
                a = b;
                b = tmp;
            }
            return a;
        }

        static int lcm(int a,int b){
              //2
	      return a / gcd(a,b) * b;
        }

        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            PrintWriter out = new PrintWriter(System.out);
            int a=in.nextInt(),b = in.nextInt();
            out.println(lcm(a,b));
            out.flush();
        }
        

Код реализации на C++:

          #include <iostream>

          using namespace std;

          int gcd(int a,int b)
          {
              //1
              while (b != 0) {
                  int tmp = a % b;
                  a = b;
                  b = tmp;
              }
              return a;
          }
          int lcm(int a,int b){
              //2
	      return a / gcd(a,b) * b;
          }

          int main()
          {
              int a, b;
              cin >> a >> b;
              cout << (lcm(a,b));
              return 0;
          }
        

Пример:
14 4
Результат:
28


Яндекс.Метрика
Украина онлайн