НОК и НОД (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 для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.