Algoholic.in.ua

Решения > НОД. Алгоритм Евклида

НОД. Алгоритм Евклида JavaС++

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

Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел.


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

Алгоритм:

  1. Находим остаток от деления первого числа на второе.
  2. Значение второй переменной присваиваем первой.
  3. Второй переменной присваиваем значение остатка.

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

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

        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(gcd(a,b));
            out.flush();
        }
        

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

          #include <iostream>

          using namespace std;

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

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

Пример:
65474 565478
Результат:
38


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