Наибольший общий делитель

Материал из Циклопедии
Перейти к: навигация, поиск
← другие значения синонима НОД
Наибольший общий делитель // KhanAcademyRussian [6:14]

Наибольший общий делитель (НОД) — это наибольшее натуральное число (множитель) для заданных натуральных чисел, которому кратны эти числа.

[править] Обозначения

Введём обозначения:

a — первое натуральное число;

b — второе натуральное число;

n — наибольший общий делитель чисел a и b, обозначается НОД(a, b).

[править] Алгоритм НОД

 → Алгоритм Евклида

Входные данные: a; b.

  1. c = a; d = b
  2. Если c > d, то c = c − d
  3. Если c < d, то d = d − c
  4. Если c > d, то идти к 2
  5. n = c

Выходные данные: n.

  • Заметим, что НОД(a, b)=ab/НОК(a, b)

[править] Другие алгоритмы

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты