НОД по простым множителям

Перечислять делители больших чисел становится медленно, а разложение на простые множители позволяет сделать это быстрее. Разложим оба числа на множители: 45 — это 3 × 3 × 5, а 75 — это 3 × 5 × 5. Общие для них простые множители — одна 3 и одна 5.

Перемножим общие простые множители: 3 × 5 равно 15 — это НОД чисел 45 и 75. Простой множитель считается общим только столько раз, сколько он встречается в обоих числах: в числе 45 две тройки, а в числе 75 — только одна, поэтому в произведение входит только одна 3.

Почему это работает: общий множитель может состоять только из простых чисел, которые есть в обоих числах. Если взять каждое общее простое число столько раз, сколько позволяют оба числа, получится наибольший общий множитель. При работе со степенями возьмите каждое общее простое число с меньшим показателем: 3^2 × 5 и 3 × 5^2 дают 3 × 5.