Алгоритмы

Материал из Artem Aleksashkin's Wiki
Перейти к навигации Перейти к поиску

НОД и НОК

// fast!
func gcd(a uint, b uint) uint {
	for a != 0 && b != 0 {
		if a > b {
			a = a % b
		} else {
			b = b % a
		}
	}

	return a + b
}

func gcd2(a uint, b uint) uint {
	for a != b {
		if a > b {
			a = a - b
		} else {
			b = b - a
		}
	}

	return a + b
}

func lcm(a uint, b uint) uint {
	return (a * b) / gcd(a, b)
}