НОК и НОД (lcm и gcd) на Java

НОД (Наибольший общий делитель) или gcd (Greatest Common Divisor)
НОД — наибольшее число, которое является делителем одновременно для чисел a и b.
Реализация (Алгоритм Евклида):

long gcd(long a,long b){
	return b == 0 ? a : gcd(b,a % b);		
}

Применение:

System.out.println(gcd(10,24));//результат: 2
System.out.println(gcd(12,24));//результат: 12
System.out.println(gcd(11,24));//результат: 1

НОК (Наименьшее общее кратное) или lcm (Least Common Multiple)
НОК — наименьшее число, которое делится на a и b без остатка.
НОК можно найти через НОД по следующей формуле:
нок
Реализация:

long lcm(long a,long b){
	return a / gcd(a,b) * b;
}

Примечание: a / gcd(a,b) * b более предпочтительно, чем a * b / gcd(a,b), т.к. во втором случае при больших числах переполнение случиться намного раньше.
Применение:

System.out.println(lcm(3, 4));//результат: 12
System.out.println(lcm(3, 9));//результат: 9
System.out.println(lcm(5,12));//результат: 60

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.