НОД и НОК
Наибольший общий делитель (НОД) двух чисел находится алгоритмом Евклида: НОД(a,b) = НОД(b, a mod b) до тех пор, пока остаток не станет 0. Наименьшее общее кратное (НОК) = a × b / НОД(a,b).
Разложение числа n на простые множители: делим n поочерёдно на 2, 3, 5, 7… до тех пор, пока n > 1. Число является простым, если его единственные делители — 1 и оно само.
