Как найти число зная нод и нок. Наименьшее общее кратное НОК. Блок схема НОД алгоритма трех чисел, четырех чисел итд

Пример НОД(12,30).

• 12=30 | a==b; //в нашем случаи 12 не равно 30
• 12<30 | a
• 30 12 | a==b; b==a; //меняем местами
• 30-12=18 | a=a-b;//производим вычитание
• 18=12| a==b;//равно ли а и b
• 18<12| ab
• 18-12=6|a=a-b; //производим вычитание
• 6=12|a==b; //в нашем случаи 6 не равно 12
• 6<12|a
• 6 12| a==b; b==a; //меняем местами
• 12-6=6|a=a-b;//производим вычитание
• 6=6| a==b; //в нашем случаи 6 равно 6
• НОД(12,30)=6;

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

НОК-это число которое из двух и более натуральных чисел является наименьшим натуральным числом, которое само делится нацело, и каждое из исходных чисел.

Самый простой и быстрый способ в плане реализации программного кода, это первоначально вычислить НОД двух чисел, затем произведение исходных двух целых чисел a и b разделить на НОД. Посмотрим на примере как это выглядет. Возьмем за пример все те же цифры 12 и 30 как мы помним наибольшее общее кратное равнялось 6. НОД=6 Следовательно по формуле НОК=a*b/НОД. НОК=12*30/6=60 Есть и другие варианты вычисления НОК к примеру каноническое разложение чисел. Рассмотрим пример, первоначально нам надо выяснить какое из чисел больше, потом мы раскладываем числа на кратные 12= 2 *2* 3 , и число 30= 2 * 3 *5 Вычисляем произведение кратных чисел из числа 30, так как оно является наибольшим. В следующей операции, одинаковые цифры вычеркиваются, как это сделал я из большего меньшее, а оставшиеся кратные числа из 12 умножаются друг на друга, у нас осталось только число 2, которое умножается на произведение кратных чисел из 30, в результате вычисления вы и получите НОК. Выглядет это следующим образом НОК=2*3*5*2=60 Хорошо это можно представить в виде столбиков, как это можно видеть из рис. 2.

рис. 2

В целом ничего сложного, главное не запутаться, сейчас мы нарисуем блок схему наименьшего общего кратного (НОК).

Блок схема Наименьшего общего кратного (НОК)

рис 3.

Алгоритм работы программы описан вначале, статьи о НОК.

Но как же быть если нам надо к примеру найти НОД трех и более натуральных чисел, или найти НОК трех или более натуральных чисел. Тут ничего сложного инструкцию по нахождению НОД из 3 чисел и НОК смотрим ниже.

НОД трех чисел:

• Сравниваем все числа К примеру a
• Начинаем вычисления с больших чисел к меньшим
• Вычисляем НОД по аналогии с двумя числами a и b
• Вычисляем по аналогии чисел НОД(a,b) и с Пример: НОД(a,b,c)=НОД((НОД(a,b)),с);
• НОД(12,30,60)
• 12<30<60
• НОД(60,30)=30
• НОД(30,12)=6

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

Блок схема НОД алгоритма трех чисел, четырех чисел итд.

рис. 4

Разберем по подробнее работу программы блок схемы из рис. 4.

• У нас подается 3 числа, но их может быть сколько угодно.
• Их мы записываем в массив array.
• Выполняем метод sort(); Это мой метод он принимает массив чисел, делает сортировку по убыванию, пузырьковым методом, о нем вы можете прочитать из уроков о массивах.
• Выполняем метод nod(), который принимает первые два числа. Я создал метод по аналогии как написано выше в этой статье.
• В следующем блоке я помещаю в тело цикла метод nod(), который присваиваю возвращаемое число из метода nod() переменной a.
• Выводим результат.
• Завершаем работу программы.

.

Пока писал статью, написал программу НОК и НОД вычисления, которую можете скачать с сайта. Работа программы очень простая, достаточно в текстовое поле вписать цифры через пробел или запятую, нажать на кнопку вычислить или Enter и программа выведет результат. Программа написана на языке java. Может запускаться со всех систем.

рис 5.

Скачать калькулятор НОК и НОД .

Онлайн калькулятор позволяет быстро находить наибольший общий делитель и наименьшее общее кратное как для двух, так и для любого другого количества чисел.

Калькулятор для нахождения НОД и НОК

Найти НОД и НОК

Найдено НОД и НОК: 12197

Как пользоваться калькулятором

• Введите числа в поле для ввода
• В случае ввода некорректных символов поле для ввода будет подсвечено красным
• нажмите кнопку "Найти НОД и НОК"

Как вводить числа

• Числа вводятся через пробел, точку или запятую
• Длина вводимых чисел не ограничена , так что найти НОД и НОК длинных чисел не составит никакого труда

Что такое НОД и НОК?

Наибольший общий делитель нескольких чисел – это наибольшее натуральное целое число, на которое все исходные числа делятся без остатка. Наибольший общий делитель сокращённо записывается как НОД .
Наименьшее общее кратное нескольких чисел – это наименьшее число, которое делится на каждое из исходных чисел без остатка. Наименьшее общее кратное сокращённо записывается как НОК .

Как проверить, что число делится на другое число без остатка?

Чтобы узнать, делится ли одно число на другое без остатка, можно воспользоваться некоторыми свойствами делимости чисел. Тогда, комбинируя их, можно проверять делимость на некоторые их них и их комбинации.

Некоторые признаки делимости чисел

1. Признак делимости числа на 2
Чтобы определить, делится ли число на два (является ли оно чётным), достаточно посмотреть на последнююю цифру этого числа: если она равна 0, 2, 4, 6 или 8, то число чётно, а значит делится на 2.
Пример: определить, делится ли на 2 число 34938 .
Решение: смотрим на последнюю цифру: 8 - значит число делится на два.

2. Признак делимости числа на 3
Число делится на 3 тогда, когда сумма его цифр делится на три. Таким образом, чтобы определить, делится ли число на 3, нужно посчитать сумму цифр и проверить, делится ли она на 3. Даже если сумма цифр получилась очень большой, можно повторить этот же процесс вновь.
Пример: определить, делится ли число 34938 на 3.
Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 3, а значит и число делится на три.

3. Признак делимости числа на 5
Число делится на 5 тогда, когда его последняя цифра равна нулю или пяти.
Пример: определить, делится ли число 34938 на 5.
Решение: смотрим на последнюю цифру: 8 - значит число НЕ делится на пять.

4. Признак делимости числа на 9
Этот признак очень похож на признак делимости на тройку: число делится на 9 тогда, когда сумма его цифр делится на 9.
Пример: определить, делится ли число 34938 на 9.
Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 9, а значит и число делится на девять.

Как найти НОД и НОК двух чисел

Как найти НОД двух чисел

Наиболее простым способом вычисления наибольшего общего делителя двух чисел является поиск всех возможных делителей этих чисел и выбор наибольшего из них.

Рассмотрим этот способ на примере нахождения НОД(28, 36) :

1. Раскладываем оба числа на множители: 28 = 1·2·2·7 , 36 = 1·2·2·3·3
2. Находим общие множители, то есть те, которые есть у обоих чисел: 1, 2 и 2.
3. Вычисляем произведение этих множителей: 1·2·2 = 4 - это и есть наибольший общий делитель чисел 28 и 36.

Как найти НОК двух чисел

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

Для вычисления НОК нужно вычислить произведение исходных чисел и затем разделить его на предварительно найденный НОД. Найдём НОК для тех же чисел 28 и 36:

1. Находим произведение чисел 28 и 36: 28·36 = 1008
2. НОД(28, 36), как уже известно, равен 4
3. НОК(28, 36) = 1008 / 4 = 252 .

Нахождение НОД и НОК для нескольких чисел

Наибольший общий делитель можно находить и для нескольких чисел, а не только для двух. Для этого числа, подлежащие поиску наибольшего общего делителя, раскладывают на простые множители, затем находят произведение общих простых множителей этих чисел. Также для нахождение НОД нескольких чисел можно воспользоваться следующим соотношением: НОД(a, b, c) = НОД(НОД(a, b), c) .

Аналогичное соотношение действует и для наименьшего общего кратного чисел: НОК(a, b, c) = НОК(НОК(a, b), c)

Пример: найти НОД и НОК для чисел 12, 32 и 36.

1. Cперва разложим числа на множители: 12 = 1·2·2·3 , 32 = 1·2·2·2·2·2 , 36 = 1·2·2·3·3 .
2. Найдём обшие множители: 1, 2 и 2 .
3. Их произведение даст НОД: 1·2·2 = 4
4. Найдём теперь НОК: для этого найдём сначала НОК(12, 32): 12·32 / 4 = 96 .
5. Чтобы найти НОК всех трёх чисел, нужно найти НОД(96, 36): 96 = 1·2·2·2·2·2·3 , 36 = 1·2·2·3·3 , НОД = 1·2·2·3 = 12 .
6. НОК(12, 32, 36) = 96·36 / 12 = 288 .

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

Обозначение : НОД(А; В) .

ПРИМЕР . Найдем НОД чисел 4 и 6.

• Число 4 без остатка делится на: 1, 2 и 4.
• Число 6 без остатка делится на: 1, 2, 3 и 6.
• Наибольшим общим делителем чисел 4 и 6 будет число 2.
• НОД(4;6) = 2

Это простой пример. А как быть с большими числами, для которых надо отыскать НОД?

В таких случаях числа раскладываются на простые множители, после чего одинаковые множители в обоих разложениях отмечаются - произведение отмеченных простых множителей и составит НОД.

ПРИМЕР . Найдем НОД чисел 81 и 45.

81 = 3 · 3 · 3 · 3 45 = 3 · 3 · 5 НОД(81;45) = 3 · 3 = 9

В тех случаях, когда у двух чисел нет одинаковых простых множителей, единственным натуральным числом, на которое нацело будут делиться такие числа будет 1. НОД таких чисел = 1. Например: НОД (7;15) = 1.

Что такое НОК

Число А называют кратным числу В, если А делится на В без остатка (нацело). Например, 10 делится нацело на 5, поэтому, 10 кратно 5; 11 не делится нацело на 5, поэтому, 11 не кратно 5.

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

Обозначение : НОК(А; В) .

Правило отыскания НОК:

• разложить оба числа на простые множители, отметить одинаковые простые множители в обоих разложениях, если таковые имеются;
• произведение всех простых множителей одного из чисел (собственно, само число) и всех не отмеченных множителей другого числа составят НОК.

ПРИМЕР . Найдем НОК чисел 81 и 45.

81 = 3 · 3 · 3 · 3 45 = 3 · 3 · 5 НОК(81;45) = 81 · 5 = 405

405 является наименьшим кратным для чисел 81 и 45: 405/81 = 5; 405/45 = 9.

Если у двух чисел нет одинаковых простых множителей, то НОК для таких чисел будет равен произведению этих чисел.

14 = 2 · 7 15 = 3 · 5 НОК(14;15) = 14 · 15 = 210

Решим задачу. У нас есть два типа печенья. Одни шоколадные, а другие простые. Шоколадных 48 штук, а простых 36. Необходимо составить из этого печенья максимально возможное число подарков, при этом надо использовать их все.

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

Получаем,

• 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
• 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Найдем среди делителей общие, которые есть как у первого, так и у второго числа.

Общими делителями будут: 1, 2, 3, 4, 6, 12.

Наибольшим из всех общих делителей является число 12. Это число называют наибольшим общим делителем чисел 36 и 48.

Исходя из полученного результата, можем заключить, что из всего печенья можно составить 12 подарков. В одном таком подарке будет 4 шоколадных печенья и 3 обычных печенья.

Определение наибольшего общего делителя

• Наибольшее натуральное число, на которое делятся без остатка два числа a и b, называют наибольшим общим делителем этих чисел.

Иногда для сокращения записи используют аббревиатуру НОД.

Некоторые пары чисел имеют в качестве наибольшего общего делителя единицу. Такие числа называют взаимно простыми числами. Например, числа 24 и 35. Имеют НОД =1.

Как найти наибольший общий делитель

Для того чтобы найти наибольший общий делитель не обязательно выписывать все делители данных чисел.

Можно поступить иначе. Сначала разложить на простые множители оба числа.

• 48 = 2*2*2*2*3,
• 36 = 2*2*3*3.

Теперь из множителей, которые входят в разложение первого числа, вычеркнем все те, которые не входят в разложение второго числа. В нашем случае это две двойки.

• 48 = 2*2*2*2*3 ,
• 36 = 2*2*3 *3.

Останутся множители 2, 2 и 3. Их произведение равно 12. Это число и будет являться наибольшим общим делителем чисел 48 и 36.

Это правило можно распространить на случай с тремя, четырьмя и т.д. числами.

Общая схема нахождения наибольшего общего делителя

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

Чтобы научиться находить наибольший общий делитель двух или нескольких чисел, необходимо разобраться с тем, что представляют из себя натуральные, простые и сложные числа.

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

Если натуральное число можно разделить только на само себя и единицу, то его называют простым.

Все натуральные числа можно разделить на себя и единицу, однако единственным четным простым числом является 2, все остальные можно поделить на двойку. Поэтому простыми могут быть только нечетные числа.

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

Большинство натуральных чисел могут делиться не только на единицу, самих себя, но и на другие числа. Так, например, число 15 можно поделить еще на 3 и 5. Все их называют делителями числа 15.

Таким образом, делитель любого А - это число, на которое оно может быть разделено без остатка. Если у числа имеется более двух натуральных делителей, его называют составным.

У числа 30 можно выделить такие делители, как 1, 3, 5, 6, 15, 30.

Можно заметить, что 15 и 30 имеют одинаковые делители 1, 3, 5, 15. Наибольший общий делитель этих двух чисел - 15.

Таким образом, общим делителем чисел А и Б называется такое число, на которое можно поделить их нацело. Наибольшим можно считать максимальное общее число, на которое можно их разделить.

Для решения задач используется такая сокращенная надпись:

НОД (А; Б).

Например, НОД (15; 30) = 30.

Чтобы записать все делители натурального числа, применяется запись:

Д (15) = {1, 3, 5, 15}

НОД (9; 15) = 1

В данном примере у натуральных чисел имеется только один общий делитель. Их называют взаимно простыми, соответственно единица и является их наибольшим общим делителем.

Как найти наибольший общий делитель чисел

Чтобы найти НОД нескольких чисел, нужно:

Найти все делители каждого натурального числа по отдельности, то есть разложить их на множители (простые числа);

Выделить все одинаковые множители у данных чисел;

Перемножить их между собой.

Например, чтобы вычислить наибольший общий делитель чисел 30 и 56, нужно записать следующее:

Чтобы не путаться при , удобно записывать множители при помощи вертикальных столбиков. В левой части от черты нужно разместить делимое, а в правой - делитель. Под делимым следует указать получившееся частное.

Так, в правом столбце окажутся все нужные для решения множители.

Одинаковые делители (найденные множители) можно для удобства подчеркнуть. Их следует переписать и перемножить и записать наибольший общий делитель.

НОД (30; 56) = 2 * 5 = 10

Вот так просто на самом деле найти наибольший общий делитель чисел. Если немного потренироваться, делать это можно будет практически на автомате.