Как найти нок чисел методом перебора

НОД, НОД

НОД — это наибольший общий делитель.

НОК — это наименьшее общее кратное.

Определения:

1. Наибольшим общим делителем чисел a и b называется наибольшее число, на которое a и b делятся без остатка.
2. Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка

Способы нахождения НОД двух чисел:

1 способ (следует из определения): Метод полного перебора для нахождения наибольшего общего делителя (НОД)  натуральных чисел.

1. Выписываем все делители числа а;
2. Выписываем все делители числа b;
3. Выбираем среди них общие делители;
4. Среди общих делителей выбираем самое большое число – это и есть НОД(a, b).

2 способ : Метод перебора делителей меньшего числа для нахождения наибольшего общего делителя (НОД)  натуральных чисел.

1. Найти делители меньшего из данных чисел.
2. Найти, начиная с большего, тот из выписанных делителей, который является также делителем другого числа.
3. Записать найденное число – НОД.

3 способ; Метод нахождения наибольшего общего делителя (НОД) натуральных чисел с помощью разложения на множители.

1. Находим разложение чисел на простые множители.
2. Подчеркиваем общие числа.
3. Находим произведение подчеркнутых чисел у одного числа.
4. Записываем ответ.

4 способ: Алгоритм Евклида нахождения наибольшего общего делителя (НОД)  двух натуральных чисел вычитанием.

1. Из большего числа вычитается меньшее.
2. Если получается 0, то числа равны друг другу и являются наибольшим общим делителем.
3. Если результат вычитания не равен 0, то большее число заменяется на результат вычитания.
4. Переход к пункту 1.

Способы нахождения НОК двух чисел:

1 способ: Метод перебора
1.    Выписываем в строчку кратные для каждого из чисел, пока не найдётся кратное, одинаковое для обоих чисел.

2 способ; Метод нахождения наибольшего общего делителя (НОД) натуральных чисел с помощью разложения на множители

1.  Разложить данные числа на простые множители.
2.  Выписать в строчку множители, входящие в разложение самого большого из чисел, а под ним – разложение остальных чисел.
3.  Подчеркнуть в разложении меньшего числа множители, которые не вошли в разложение бóльшего числа и добавить эти множители в разложение большего числа. 
4.  Полученное произведение записать в ответ. 

    Свойства наибольшего общего делителя:

1. НОД(a, b) = НОД(b, a)
2. НОД(a, b) = НОД(-a, b)
3. НОД(a, b) = НОД(|a|,|b|)
4. НОД(a, 0) = |a|
5. НОД(a, к • a) = |a|, при любом к ∈ Z
6. НОД(a, НОД(b, с)) = НОД(НОД(a, b), c)

Свойства наименьшего общего кратного:

1. НОК(a, b) = НОК(b, a)
2. НОД(a, b) = НОД(-a, b)
3. НОД(a, b) = НОД(|a|,|b|)
4. НОК(a, НОК(b, с)) = НОК(НОК(a, b), c)

ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

СРЕДНЯЯ
ОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 377

КИРОВСКОГО
РАЙОНА САНКТ-ПЕТЕРБУРГА

Тема: «НОД и
НОК.»

Памятка
по математике

Для
учеников 5 класса

Автор:
Кудрявцева Лилия Викторовна

НОД и НОК

9

1, 3, 9                                           18, 27, 36, 45 …

НОД	НОК
Наибольший общий делитель (НОД) двух данных чисел a и b – это наибольшее число, на которое оба числа a и b делятся без остатка.	Наименьшим общим кратным (НОК) двух и более натуральных чисел называется наименьшее натуральное число, которое делится нацело на каждое из этих чисел.
I способ нахождения НОД методом перебора делителей 1. Найти делители каждого числа; 2. Найти общие делители; 3. Выбрать наибольший общий делитель. Найти НОД 10 и 15. Д (10) = {1, 2, 5, 10} Д (15) = {1, 3, 5, 15} Д (10, 15) = {1, 5} НОД (10; 15) = 5	I способ нахождения НОК методом перебора кратных 1. Берем большее из чисел 2. Находим числа кратные выбранному (умножая выбранное число последовательно на 1, 2, 3, 4, 5 , и тд) 3. Каждое полученное кратное проверяем делится ли оно на оставшиеся число; первое такое кратное и есть НОК. Найти НОК 18 и 24 24•1=24  (не делится на 18) 24•2=48   (не делится на 18) 24•3=72  –  делится на 18 НОК (24, 18)=72
II способ нахождения НОД через разложения на простые множители 1. Разложить числа на простые множители; 2. Подчеркнуть одинаковые простые множители в  обоих числах; 3. Найти произведение одинаковых простых множителей и записать ответ. Найти НОД  48 и 36. НОД (48; 36) = 2 • 2 • 3 = 12	II способ нахождения НОК через разложения на простые множители 1. Разложить на простые множители каждое число; 2. Выписать все множители из разложения одного любого числа; 3. Добавить к ним недостающие множители из разложения другого числа; 4. Найти произведение получившихся множителей. Найти НОК  24 и 60. 60 = 2 • 2 • 3 • 5   24 = 2 • 2 • 2 • 3                                                                 60 НОК (24; 60) = 2 • 2 • 3 • 5 • 2 =120
Примечание 1: Если a и b взаимно простые* числа, то НОД(a,b)=1 Например:     НОД(4,9)=1	Примечание 1: Если a и b взаимно простые* числа, то НОК(a,b)=a•b Например:     НОК(4, 9)=4•9=36
Примечание 2:  Если a делится на b, то НОД(a,b)=b Например: НОД(120, 60)=60	Примечание 2:  Если a делится на b, то НОК(a,b)=a Например: НОК(120, 60)=120

*Взаимно
простые числа – это те, у которых нет общих
простых делителей. (Например: 4 и 9)

Примечание 1:  Простые числа (1,2,3,5,7,11,13,17 и т.д.) –
взаимно просты

Примечание 2:  Два соседних
натуральных числа (например:  24 и 25) –  взаимно просты

Светило науки – 213 ответов – 5321 помощь

НОД и НОК

Взаимно простые числа – это те, у которых нет общих простых делителей. (Например: 4 и 9)

Примечание 1: Простые числа (1,2,3,5,7,11,13,17 и т.д.) – взаимно просты

Примечание 2: Два соседних натуральных числа (например: 24 и 25) – взаимно просты

Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё1 более мелкие задачи. В олимпиадных задачах по программированию очень часто требуется найти НОД(наибольший общий делитель) или НОК(наименьшее общее кратное) двух или более чисел. Это может быть задача по фасовке предметам по ящикам (целочисленное деление) или формирование людей в бригады. Короче там где нужно искать целые числа после деления.

Пример двух чисел 6 и 15. Очевидно, что НОД (наибольшим общим делителем) будет число 3. А далее находим НОК (наименьшее) общее кратное). Которое будет равно 30.

Для небольших чисел это легко вычисляется в уме. Но вот с пятиначными числами, так легко не получится. Поэтому предлагаю обратиться к алгоритму Евклида. Математические выкладки и детали в данной статье затрагивать не буду, хотя там много есть интересного.

Но суть достаточно простая. Их двух чисел выбираем большее и аычитаем из него меньшее. Далее выбираем снова большое и вычитаем из него снова, до тех пор пока разница не будет равна одному из чисел. Это и будет искомое число. Предлагаю проверить сперва на очевидных примерха.

Мы с вами уже находили НОД для 6 и 15. И у нас также получилось 3.

Теперь возьмём числа побольше. Я конечно могу сказать, что беру случайные числа, но по факту могы их проверить.

Пусть будут числа 195 и 1450. Очевидно, что они точно деляться на 5, но я предлагаю проверить.

И действительно 195 = 3*5*13, а 1450 = 2*5*5*29.

А теперь рассмотрим как найти НОК (наименьшее общее кратное). Рассмотрим сперва на простом примере. Числа 15 и 6.

Есть такая замечательная формула НОК = (A*B) / НОД.

Теперь проверим это выражение. НОК = (15*6)/3=30.

Оказывается, что всё достаточно просто. Если рассмотреть числа 195 и 1450, то для них НОК будет 195*1450/5=56550 или 2*3*5*5*13*29.

То есть без калькулятора можно свободно найти НОД и НОК. Естественно что для программиста эта задача становится очень простой.

Для начала разберем алгоритм через блок-схему.

Подробнее можно увидеть на видео:

У меня всё, благодарю за внимание.

———————————————————————-

Делюсь другими материалами:

Сериал Дистанционка от коллег в А1: Дистанционка. Серия 1. Дистанционка. Серия 2. Дистанционка. Серия 3.

Материалы по Scratch.