Наибольший общий делитель и наименьшее общее кратное

Июль 29, 2022

Главная
Математика
Наибольший общий делитель и наименьшее общее кратное

Содержание

2. НОД и НОК НОД (GCD) – наибольший общий делитель. Пример: НОД(18, 12) = 6 НОК (LCM)
3. Алгоритм Евклида Алгоритм Евклида работает за O(log min(a, b))
4. Простые числа Простые числа – это натуральные числа, имеющие ровно два различных натуральных делителя Например, 2,
5. Наивный метод
6. Реальный метод
8. Скачать презентацию

Слайд 2

НОД и НОК
НОД (GCD) – наибольший общий делитель. Пример: НОД(18, 12)

= 6
НОК (LCM) – наименьшее общее кратное. Пример: НОК(18, 12) = 36

Слайд 3

Алгоритм Евклида
Алгоритм Евклида работает за O(log min(a, b))

Слайд 4

Простые числа
Простые числа – это натуральные числа, имеющие ровно два различных

натуральных делителя Например, 2, 3, 5, 7, 11 и т.д.
На олимпиадах часто встречаются задачи, для решения которых нужно определить, является ли заданное число простым.

Слайд 5

Наивный метод

Слайд 6

Реальный метод