Программа на Java для поиска НОД и НОК двух чисел с использованием алгоритма Евклида

Опубликовано: 1 Декабря, 2021

НОД или наибольший общий делитель двух заданных чисел A и B - это наибольшее число, делящее A и B полностью, т.е. оставляя остаток 0 в каждом случае. НОК или наименьшее общее кратное двух заданных чисел A и B - это наименьшее число, которое можно разделить как на A, так и на B, оставляя остаток 0 в каждом случае.

НОК двух чисел можно вычислить в подходе Евклида, используя НОД для A и B.

LCM(A, B) = (a * b) / GCD(A, B)

Примеры:

Input : A = 20, B = 30
Output:
GCD = 10
LCM = 60
Explanation:
The highest number which divides 20 and 30 is 10. So the GCD of 20, 30 is 10.
The lowest number that can be divided by 20 and 30, leaving remainder 0 is 60.
So the LCM of 20 and 30 is 60.
Input : A= 33, B= 40
Output:
GCD = 1
LCM = 1320

Евклидов алгоритм вычисления НОД:

Этот подход к вычислению НОД основан на том принципе, что НОД двух чисел A и B остается неизменным, даже если большее число заменяется модулем A и B. В этом подходе мы выполняем операцию НОД для A и B несколько раз, заменяя A на B и B по модулю A и B, пока модуль не станет 0.

Ниже приведена реализация поиска НОД и НОК двух чисел с использованием алгоритма Евклида:

Ява

 // Java program to compute
 // GCD of two numbers
 // using Euclid's algorithm
 
import java.io.*;
 
class GFG {
 
    // gcd method returns the GCD of a and b
    static int gcd( int a, int b) {
       
        // if b=0, a is the GCD
        if (b == 0 )
            return a;
       
        // call the gcd() method recursively by
        // replacing a with b and b with
        // modulus(a,b) as long as b != 0
        else
            return gcd(b, a % b);
    }
 
    // lcm() method returns the LCM of a and b
    static int lcm( int a, int b, int gcdValue)
    {
        return Math.abs(a * b) / gcdValue;
    }
 
    // Driver method
    public static void main(String[] args) {
 
        int a = 20 , b = 30 , gcdValue;
        gcdValue = gcd(a, b);
       
        // calling gcd() over
        System.out.println( "GCD = " + gcdValue);
       
        // calling lcm() over integers 30 and 20
        System.out.println( "LCM = " + lcm(a, b, gcdValue));
    }
 }

Выход

 НОД = 10
НОК = 60

Вниманию читателя! Не прекращайте учиться сейчас. Ознакомьтесь со всеми важными концепциями Java Foundation и коллекций с помощью курса "Основы Java и Java Collections" по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Technical Scripter Picked Java

Программа на Java для поиска НОД и НОК двух чисел с использованием алгоритма Евклида

Евклидов алгоритм вычисления НОД:

Ява

РЕКОМЕНДУЕМЫЕ СТАТЬИ