Как найти нод двух чисел онлайн калькулятор. Вычислить нод
НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ, алгоритм как найти НОД
Наибольший общий делитель чисел – это наибольшее число, на которое делятся все заданные числа.
Алгоритм поиска НОД
Вычисление НОД похоже на поиск НОК. Чтобы найти наибольший общий делитель, нужно использовать следующий алгоритм:
- Разложить все числа на простые множители, используя признаки делимости чисел.
- Найти совпадающие множители во всех числах и выписать их.
- Перемножить совпадающие множители.
Если среди множителей чисел не были найдены одинаковые, числа являются взаимно простыми.
Примеры поиска наибольшего общего делителя
Рассмотрим, как найти НОД с помощью алгоритма на нескольких примерах.
Пример 1:
Найдите наибольший общий делитель чисел 420 и 990.
Решение:
Разложим оба числа на простые множители:
Получили, что:
420 = 2 ⋅ 2 ⋅ 3 ⋅ 5 ⋅ 7
990 = 2 ⋅ 3 ⋅ 3 ⋅ 5 ⋅ 11
Выпишем все совпадающие множители для обоих чисел и перемножим их:
НОД = 2 ⋅ 3 ⋅ 5 = 30
Ответ: 30
Пример 2:
Найдите наибольший общий делитель чисел 588 и 1820.
Решение:
Разложим оба числа на простые множители:
Получили, что:
588 = 2 ⋅ 2 ⋅ 3 ⋅ 7 ⋅ 7
1820 = 2 ⋅ 2 ⋅ 5 ⋅ 7 ⋅ 13
Выпишем все совпадающие множители для обоих чисел и перемножим их:
НОД = 2 ⋅ 2 ⋅ 7 = 28
Ответ: 28Пример 3:
Найдите наибольший общий делитель чисел 1000 и 3267.
Решение:
Разложим оба числа на простые множители:
Получили, что:
1000 = 2 ⋅ 2 ⋅ 2 ⋅ 5 ⋅ 5 ⋅ 5
3267 = 3 ⋅ 3 ⋅ 3 ⋅ 11 ⋅ 11
Совпадающих множителей у этих 2 чисел нет, поэтому они являются взаимно простыми, то есть
Ответ: 1Калькулятор НОД и НОК с решением онлайн
Найдем наибольший общий делитель НОД (36 ; 24)Этапы решения
Способ №1
1) Разложим числа на простые множители. Для этого проверим, является ли каждое из чисел простым (если число простое, то его нельзя разложить на простые множители, и оно само является своим разложением)
36 - составное число24 - составное число
Разложим число 36 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
36 : 2 = 18 - делится на простое число 218 : 2 = 9 - делится на простое число 29 : 3 = 3 - делится на простое число 3. Завершаем деление, так как 3 простое число
Разложим число 24 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
24 : 2 = 12 - делится на простое число 212 : 2 = 6 - делится на простое число 26 : 2 = 3 - делится на простое число 2. Завершаем деление, так как 3 простое число
2) Выделим синим цветом и выпишем общие множители
36 = 2 ⋅ 2 ⋅ 3 ⋅ 3 24 = 2 ⋅ 2 ⋅ 2 ⋅ 3 Общие множители (36 ; 24) : 2, 2, 3
3) Теперь, чтобы найти НОД нужно перемножить общие множители
Ответ: НОД (36 ; 24) = 2 ∙ 2 ∙ 3 = 12
Способ №2
1) Найдем все возможные делители чисел (36 ; 24). Для этого поочередно разделим число 36 на делители от 1 до 36, число 24 на делители от 1 до 24. Если число делится без остатка, то делитель запишем в список делителей.
Для числа 36 выпишем все случаи, когда оно делится без остатка:36 : 1 = 36;36 : 2 = 18;36 : 3 = 12;36 : 4 = 9;36 : 6 = 6;36 : 9 = 4;36 : 12 = 3;36 : 18 = 2;36 : 36 = 1;
Для числа 24 выпишем все случаи, когда оно делится без остатка:24 : 1 = 24;24 : 2 = 12;24 : 3 = 8;24 : 4 = 6;24 : 6 = 4;24 : 8 = 3;24 : 12 = 2;24 : 24 = 1;
2) Выпишем все общие делители чисел (36 ; 24) и выделим зеленым цветом самы большой, это и будет наибольший общий делитель НОД чисел (36 ; 24)
Общие делители чисел (36 ; 24): 1, 2, 3, 4, 6, 12
Ответ: НОД (36 ; 24) = 12
Найдем наименьшее общее кратное НОК (52 ; 49)Этапы решения
Способ №1
1) Разложим числа на простые множители. Для этого проверим, является ли каждое из чисел простым (если число простое, то его нельзя разложить на простые множители, и оно само является своим разложением)
52 - составное число49 - составное число
Разложим число 52 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
52 : 2 = 26 - делится на простое число 226 : 2 = 13 - делится на простое число 2. Завершаем деление, так как 13 простое число
Разложим число 49 на простые множители и выделим их зелены цветом. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
49 : 7 = 7 - делится на простое число 7. Завершаем деление, так как 7 простое число
2) Прежде всего запишем множители самого большого числа, а затем меньшего числа. Найдем недостающие множители, выделим синим цветом в разложении меньшего числа множители, которые не вошли в разложение большего числа.
52 = 2 ∙ 2 ∙ 1349 = 7 ∙ 7
3) Теперь, чтобы найти НОК нужно перемножить множители большего числа с недостающими множителями, которые выделены синим цветом
НОК (52 ; 49) = 2 ∙ 2 ∙ 13 ∙ 7 ∙ 7 = 2548
Способ №2
1) Найдем все возможные кратные чисел (52 ; 49). Для этого поочередно умножим число 52 на числа от 1 до 49, число 49 на числа от 1 до 52.
Выделим все кратные числа 52 зеленым цветом:
52 ∙ 1 = 52; 52 ∙ 2 = 104; 52 ∙ 3 = 156; 52 ∙ 4 = 208;52 ∙ 5 = 260; 52 ∙ 6 = 312; 52 ∙ 7 = 364; 52 ∙ 8 = 416;52 ∙ 9 = 468; 52 ∙ 10 = 520; 52 ∙ 11 = 572; 52 ∙ 12 = 624;52 ∙ 13 = 676; 52 ∙ 14 = 728; 52 ∙ 15 = 780; 52 ∙ 16 = 832;52 ∙ 17 = 884; 52 ∙ 18 = 936; 52 ∙ 19 = 988; 52 ∙ 20 = 1040;52 ∙ 21 = 1092; 52 ∙ 22 = 1144; 52 ∙ 23 = 1196; 52 ∙ 24 = 1248;52 ∙ 25 = 1300; 52 ∙ 26 = 1352; 52 ∙ 27 = 1404; 52 ∙ 28 = 1456;52 ∙ 29 = 1508; 52 ∙ 30 = 1560; 52 ∙ 31 = 1612; 52 ∙ 32 = 1664;52 ∙ 33 = 1716; 52 ∙ 34 = 1768; 52 ∙ 35 = 1820; 52 ∙ 36 = 1872;52 ∙ 37 = 1924; 52 ∙ 38 = 1976; 52 ∙ 39 = 2028; 52 ∙ 40 = 2080;52 ∙ 41 = 2132; 52 ∙ 42 = 2184; 52 ∙ 43 = 2236; 52 ∙ 44 = 2288;52 ∙ 45 = 2340; 52 ∙ 46 = 2392; 52 ∙ 47 = 2444; 52 ∙ 48 = 2496;52 ∙ 49 = 2548;
Выделим все кратные числа 49 зеленым цветом:
49 ∙ 1 = 49; 49 ∙ 2 = 98; 49 ∙ 3 = 147; 49 ∙ 4 = 196;49 ∙ 5 = 245; 49 ∙ 6 = 294; 49 ∙ 7 = 343; 49 ∙ 8 = 392;49 ∙ 9 = 441; 49 ∙ 10 = 490; 49 ∙ 11 = 539; 49 ∙ 12 = 588;49 ∙ 13 = 637; 49 ∙ 14 = 686; 49 ∙ 15 = 735; 49 ∙ 16 = 784;49 ∙ 17 = 833; 49 ∙ 18 = 882; 49 ∙ 19 = 931; 49 ∙ 20 = 980;49 ∙ 21 = 1029; 49 ∙ 22 = 1078; 49 ∙ 23 = 1127; 49 ∙ 24 = 1176;49 ∙ 25 = 1225; 49 ∙ 26 = 1274; 49 ∙ 27 = 1323; 49 ∙ 28 = 1372;49 ∙ 29 = 1421; 49 ∙ 30 = 1470; 49 ∙ 31 = 1519; 49 ∙ 32 = 1568;49 ∙ 33 = 1617; 49 ∙ 34 = 1666; 49 ∙ 35 = 1715; 49 ∙ 36 = 1764;49 ∙ 37 = 1813; 49 ∙ 38 = 1862; 49 ∙ 39 = 1911; 49 ∙ 40 = 1960;49 ∙ 41 = 2009; 49 ∙ 42 = 2058; 49 ∙ 43 = 2107; 49 ∙ 44 = 2156;49 ∙ 45 = 2205; 49 ∙ 46 = 2254; 49 ∙ 47 = 2303; 49 ∙ 48 = 2352;49 ∙ 49 = 2401; 49 ∙ 50 = 2450; 49 ∙ 51 = 2499; 49 ∙ 52 = 2548;
2) Выпишем все общие кратные чисел (52 ; 49) и выделим зеленым цветом самое маленькое, это и будет наименьшим общим кратным чисел (52 ; 49).
Общие кратные чисел (52 ; 49): 2548
Ответ: НОК (52 ; 49) = 2548
matematika-club.ru
Нод и Нок чисел. Разложение на простейшие множители. Примеры вычисление НОК И НОД.
Для начала вспомним, что такое простые числа – это числа, которые имеют два делителя: само себя и \(1\). Давайте рассмотрим два числа \(18\) и \(48\) и найдем числа которые будут делится без остатка на них – \(864\) и \(144\). Наименьшее из них \(144\), то есть мы нашли наименьшее общее кратное, сокращенно \(НОК\). Когда мы вычисляем \(НОК\) двух чисел, мы записываем их в круглых скобках \(НОК\)\((48;18).\) А если у нас очень большие числа, как нам тогда искать \(НОК\)? Для этого мы каждое число должны разложить на простые множители. Взять множители разложения большего числа и недостающие из второго и перемножить их.
НОК\((48;18)=2*3*4*2*3=144.\)
Давайте найдем \(НОК\) у \(7\) и \(9\). Раскладываем на простые множители:
\(7\) и \(17\) – это простые числа, так как они делятся на себя и на \(1\), то есть общий делитель у них \(1\). Два числа называются взаимно простыми, если у них нет общих делителей, кроме числа \(1\). Как же нам в этом случае найти \(НОК\)? Применяем все те же правила. Берем простые множители из наибольшего числа и недостающие из второго и затем перемножаем их. \(НОК\) чисел \(17\) и \(7\) равен их произведению, то есть \(119\). Можно сформулировать простое правило для нахождения \(НОК\) у взаимно простых чисел:
Чтобы найти \(НОК\) у взаимно простых чисел, мы должны перемножить их. Легко, не так ли?
Задача 1. Найти \(НОК\)(840;140).
Раскладываем на простые множители:
Заметив, что множители в числе \(140\) повторяются, берем множители разложение большего числа: \(2*2*3*5*7*2=840.\)
Ответ: \(НОК\)\((840;140)=840.\)
Далее введем понятие наибольшего общего делителя, сокращенно \(НОД\). Для его нахождения нужно также разложить на простые сомножители и перемножить их общие цифры.
Задача 2. Найти \(НОД\)(840;140).
Решение. Выше можно посмотреть разложение этих чисел на простые множители.
Общие множители это 2*5*2*7=140.
Ответ: \(НОД\)(840;140)=140.
Больше уроков и заданий по математике вместе с преподавателями нашей онлайн-школы "Альфа". Запишитесь на пробное занятие уже сейчас!
Запишитесь на бесплатное тестирование знаний!
myalfaschool.ru
Алгоритм Евклида - нахождение наибольшего общего делителя
Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.
Алгоритм нахождения НОД делением
- Большее число делим на меньшее.
- Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
- Если есть остаток, то большее число заменяем на остаток от деления.
- Переходим к пункту 1.
Пример:Найти НОД для 30 и 18.30/18 = 1 (остаток 12)18/12 = 1 (остаток 6)12/6 = 2 (остаток 0). Конец: НОД – это делитель. НОД (30, 18) = 6
Исходный код на Python
a = 50 b = 130 while a!=0 and b!=0: if a > b: a = a % b else: b = b % a print (a+b)Примечание к коду. В цикле в a или b записывается остаток от деления. Когда остатка нет (мы не знаем в а он или b, поэтому проверяем оба условия), то цикл завершается. В конце выводится сумма a и b, т.к. мы не знаем, в какой переменной записан НОД, а в одной из них в любом случае 0, который на результат суммы никак не влияет.
Алгоритм нахождения НОД вычитанием
- Из большего числа вычитаем меньшее.
- Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
- Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
- Переходим к пункту 1.
Пример:Найти НОД для 30 и 18.30 - 18 = 1218 - 12 = 612 - 6 = 66 – 6 = 0 Конец: НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6
Исходный код на Python
a = 50 b = 130 while a != b: if a > b: a = a - b else: b = b - a print (a)Оформление кода в виде функции
def gcd(a,b): while a != b: if a > b: a = a - b else: b = b - a print (a)Блок-схема "Алгоритм Евклида"
younglinux.info
Как найти нод двух чисел онлайн калькулятор – нок формула
Похоже, вы используете блокировщик рекламы. Наш сайт существует и развивается только за счет дохода от рекламы.
Пожалуйста, добавьте нас в исключения блокировщика.
Скрыть меню
На главную страницу Войти при помощи
Темы уроков
Начальная школа Математика 5 класс Математика 6 класс Алгебра 7 класс Алгебра 8 класс Алгебра старшая школа
Учитесь у всех, не подражайте никому. Максим Горький
на главную
Наибольший общий делитель онлайн
Найти репетитора←Вернуться в «Калькуляторы онлайн»
Здесь будет решение… |
Данный калькулятор поможет вам проверить ваши вычисления при расчёте наибольшего общего делителиля (НОД).
Инструкции к калькулятору
- Введите натуральные числа через пробел или запятую в текстовое поле внизу. (Например: 60, 7, 12, 23)
- Нажмите кнопку «Найти НОД» и ожидайте результата на экране ниже.
- Убедитесь, что среди введённых чисел нет нулей.
Важно!
Данный калькулятор поиска онлайн НОД может служить лишь для проверки ваших вычислений. Научиться находить НОД (наибольший общий делитель) самостоятельно можно в теме нахождение наибольшего общего делителиля.
По крайней мере, общие кратные
Несколько раз
Зонт, который разделен на конкретный диспенсер без остатка, называется иначе несколько раз. Например, 48 кратных 8, число 48 является кратным, а число 8 является делителем.
Число может быть бесчисленным, но несколько номеров одновременно называют таким числом общий множественный.
Например, число 77 кратно числам: 1, 7, 11, 77.
Другой пример.
Самый большой общий делитель
Числа 3 кратны 12, 15, 24, 27, 30 и т. Д. Числа 5 кратны 10, 15, 25, 30, 35 и т. Д. На рисунках 3 и 5 имеются общие множители 15 и 30.
Обнаружение общего множественного числа довольно просто, вы можете просто умножить заданные числа, что делает произведение этих чисел общим кратным им.
NOC
Из суммарных множителей для данных чисел наиболее интересным является наименьшее общее кратное.
По крайней мере, общие кратные (сокращенно NOC) нескольких номеров, наименьшее число выделяется для каждого из этих чисел на единицу.
Например, для трех чисел: 3, 5 и 12 наименьшее общее число равно 60, так как никакое другое число менее 60 не делится на 3, 5 и 12.
Обычно наименьшее общее часто записывается как: LCM (a, b, …) = x.
На этом фоне мы напишем наименьший общий кратный числам 3, 5 и 12:
NOC (3, 5, 12) = 60.
Калькулятор NOC
Этот калькулятор поможет вам найти хотя бы общее количество цифр.
Просто введите числа с пробелом или запятой и нажмите кнопку.
Кратное число — это число, делащееся на данное целое число без остатка; например 12 кратно 3.
Найти, вычислить кратные с калькулятором
Калькулятор
Как пользоваться калькулятором
Данный калькулятор позволяет расчитать кратные чисел до ста его значений.В поле с исходным значением XX введите число, кратное которого требуется вычислить, затем нажмите на кнопку Вычислить для того что бы калькулятор произвел расчет.
На калькуляторе можно вычислить значения таких кратных как: числа кратные 1, числа кратные 2, числа кратные 3, и т.д.
Кратное — это произведение целого числа на любое другое целое число.
Например, первые шесть чисел, кратных 3: 3, 6, 9, 12, 15 и 18. Это легко проверить на примерах ниже:
3 x 1 = 3 ; 3 x 2 = 6 ; 3 x 3 = 9 ; 3 x 4 = 12 ; 3 x 5 = 15 ; 3 x 6 = 18.
Два и более чисел могут иметь общие кратные.
Нахождение НОД и НОК онлайн
Например, наименьшее общее кратное (НОК) 3 и 7 равно 21, т. е. произведению этих двух чисел.
Наглядная таблица чисел кратных 3
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
— Кратные 3
Похоже, вы используете блокировщик рекламы.
Наибольший общий делитель
Наш сайт существует и развивается только за счет дохода от рекламы.
Пожалуйста, добавьте нас в исключения блокировщика.
Скрыть меню
На главную страницу Войти при помощи
Темы уроков
Начальная школа Математика 5 класс Математика 6 класс Алгебра 7 класс Алгебра 8 класс Алгебра старшая школа
Правильная постановка вопроса свидетельствует о некотором знакомстве с предметом.Фрэнсис Бэкон
на главную
Наименьшее общее кратное онлайн
Найти репетитора←Вернуться в «Калькуляторы онлайн»
Здесь будет решение… |
Калькулятор расчёта наименьшего общего кратного онлайн (НОК) поможет вам в нахождении общего знаменателя при сложении и вычитании обыкновенных дробей с разными знаменателями.
Инструкции к калькулятору
Важно!
Данный калькулятор поиска онлайн НОК может служить лишь для проверки ваших вычислений. Научиться находить НОК самостоятельно можно в теме нахождение наименьшего общего кратного.
Найдите наибольший общий разделитель в Интернете
Похоже, вы используете рекламный блок. Наш сайт существует и развивается только за счет доходов от рекламы.
Добавьте нас к исключениям блокировщика.
Скрыть меня
На главную страницу Войдите в систему
Темы урока
Математика начальной школы 5-й класс Математика 6-й класс Алгебра 7-й класс Алгебра 8-й класс Алгебра средней школы
Правильное утверждение по проблеме показывает некоторые знания предмета. Фрэнсис Бэкон
дома
Самый большой общий разделитель в Интернете
Найти наставника← Вернуться назад на «Калькуляторы онлайн»
Будет решение … |
Этот калькулятор поможет вам проверить расчетные расчеты самый большой общий делимый (НОД).
Инструкции для калькулятора
- В текстовом поле внизу введите натуральные числа с пробелом или запятой.
(Например: 60, 7, 12, 23)
- Нажмите «Найти GCD«И ждите результат ниже.
- Убедитесь, что между введенными номерами нет нулей.
Важно!
Этот калькулятор веб-поиска GCD может служить только для проверки ваших расчетов. Узнайте, как найти GCD (самый большой общий делитель) независимо в поиске самого большого общего делителя.
Решение математических проблем в Интернете
Все счетчики частиц
Найдите все разделители, по которым число делится без остатка. Разложение числа на основные факторы.
Простые числа и числа Фибоначчи
Первое число — это число, которое является общим и одно.
Число Фибоначчи — это число, которое мы получаем от добавления предыдущих двух.
Математическое значение
Вычисление квадратного, корневого и кубического корней числа, а также синус, косинус, тангенциальный, естественный и десятичный логарифмы.
Код Морзе
Нумерация кода в коде Морзе, с возможностью прослушивания результата.
Количество систем
Отображаемый номер во многих системах: двоичный, треугольный, восьмеричный, шестнадцатеричный.
Количество слов
Создайте текстовое имя (капитал).
Различные достопримечательности
Создает номер изображения — QR-код.
Вычислите номера MD5, SHA-1, Base64, выбор базы, дату во время UNIX.
Нумерология чисел
Определите числовое значение числа, добавив числа, которые они составляют.
Полная информация о странице бренда
Арифметические операции
Расчеты результата сложения, разности, продукта, частного, а также остатка раскола.
Взаимный и двойной
Убедитесь, что простые числа близнецов и сети являются чистыми.
NOC и GCD
Выбор наименьшего общего кратного и максимального общего числа сплиттеров.
Общими функциями являются несколько номеров
Общие делители, общее число, среднее арифметическое и геометрия, расчет гипотенузы.
vipstylelife.ru
НОД и НОК трех и более чисел
| НОД (Факторизованный вид) |
| НОК (Факторизованный вид) |
| НОД (Числовое значение) |
| НОК (Числовое значение) |
Что такое НОК?
НОК - наименьшее общее кратное. Такое число, на которое без остатка будет делится все заданные числа.
Например, если заданные числа 2, 3, 5, то НОК=2*3*5=30
А если заданные числа 2,4,8, то НОК =8
что такое НОД?
НОД - наибольший общий делитель. Такое число, которым можно разделить каждое из заданных чисел, без остатка.
Логично что если заданные числа будут простыми, то НОД равен единице.
А если заданны числа 2, 4, 8 то НОД равен 2.
НОД можно рассчитать по методу Евклида.
Расписывать его в общем виде не будем, а просто покажем решение на примере.
Заданы два числа 126 и 44. Найти НОД.
1. Делим 126 на 44 и находим остаток от деления 126=44*2+38. Остаток 38
2.Делим 44 на 38 и находим остаток. Он равен 6
3. Делим 38 на 6 и определим остаток. Остаток равен 2
4. Делим 6 на 2 и видим что он делится нацело, то есть с нулевым остатком.
Смотрим какое же было предыдущий остаток (на 3 вычислении). Видим что он равен 2
НОД этих двух чисел равен 2.
Альтернативный путь. Второй вариант который мы можем вам предложить более нагляден и понятен , и позволит визуально увидеть чем отличается НОК от НОД и как они высчитываются.
Для этого нам надо каждое число преобразовать в произведение сомножителей. Как это сделано в материале Простые множители. Теория чисел
Тогда если нам даны два числа вида
и
То НОД высчитывается как
где min - минимальное значение из всех значений степеней числа pn
а НОК как
где max - максимальное значение из всех значений степеней числа pn
Смотря на вышеприведенные формулы, можно легко доказать что НОД двух и более чисел будет равен единице, тогда когда среди хотя бы одной пары заданных значений, окажутся взаимно простые числа.
Поэтому легко ответить на вопрос чему равен НОД вот таких чисел 3, 25412, 3251, 7841, 25654, 7 ничего не вычисляя.
числа 3 и 7 взаимно простые, а следовательно НОД=1
Рассмотрим пример.
Даны три числа 24654, 25473 и 954
Каждое число раскладывается в следующие множители
Или, если мы запишем в альтернативном виде
Теперь легко высчитать НОД по формуле
То есть НОД этих трех чисел равен трем
Ну а НОК можем вычислить аналогично, и он равен
Наш бот, поможет Вам вычислить НОД и НОК любых целых чисел, двух, трех или десяти.
Удобство нашего бота не только в легкости ввода, но и в выведении результата.
Результат будет в двух видах, в виде факторизации и в виде обычного численного решения.
Факторизация нам поможет увидеть точный результат, в случае если числа будут очень большие.
Ограничение только одно, кажое число не должно быть длиннее 15 символов
Удачных расчетов!
- Нормальное интегральное распределение >>
www.abakbot.ru
Алгоритм Евклида — Науколандия
Алгоритм Евклида — это способ нахождения наибольшего общего делителя (НОД) двух целых чисел. Оригинальная версия алгоритма, когда НОД находится вычитанием, была открыта Евклидом (III в. до н. э). В настоящее время чаще при вычислении НОД алгоритмом Евклида используют деление, так как данный метод эффективнее.
Вычисление НОД делением
Наибольший общий делитель пары чисел – это самое большое число, которое нацело делит оба числа пары. Пусть требуется вычислить НОД для чисел 108 и 72. Алгоритм вычисления делением будет таковым:
- Разделим большее число (делимое) на меньшее (делитель): 108 / 72 = 1, остаток 36.
- Поскольку остаток не был равен нулю, то сделаем делитель делимым, а остаток – делителем: 72 / 36 = 2, остаток 0.
- Когда остаток равен нулю, то делитель является искомым НОД для пары заданных чисел. То есть НОД(108, 72) = 36. Действительно, 108 / 36 = 3 и 72 / 36 = 2.
В данном алгоритме деление повторяется до тех пор, пока остаток не станет равным нулю. Когда он таковым становится, НОДом является делитель последнего деления. Например, требуется найти НОД(106, 16):
- 106 / 16 = 6, остаток 10
- 16 / 10 = 1, остаток 6
- 10 / 6 = 1, остаток 4
- 6 / 4 = 1, остаток 2
- 4 / 2 = 2, остаток 0
- НОД(106, 16) = 2
Вычисление НОД вычитанием
При нахождении НОД вычитанием также требуется достичь нуля. Алгоритм схож с методом деления, только здесь на каждом следующем этапе вычитаемым и уменьшаемым становятся вычитаемое и разность из предыдущего шага. При этом всегда из большего числа вычитается меньшее. Данная разновидность алгоритма подходит только для положительных целых чисел.
Пусть требуется найти НОД(108, 72):
- 108 - 72 = 36
- 72 - 36 = 36
- 36 - 36 = 0
- НОД(108, 72) = 36
Найдем НОД(44, 60):
- 60 - 44 = 16
- 44 - 16 = 28
- 28 - 16 = 12
- 16 - 12 = 4
- 12 - 4 = 8
- 8 - 4 = 4
- 4 - 4 = 0
- НОД(44, 60) = 4
Данный алгоритм иногда описывают по-другому. Вычитание заканчивают раньше, на шаге, когда одно число нацело делит другое. То есть комбинируют вычитание с проверкой делимости. Тогда нахождение НОД для 44 и 60 будет выглядеть так:
- Делит ли 44 нацело 60? Нет. 60 - 44 = 16.
- Делит ли 16 нацело 44? Нет. 44 - 16 = 28.
- Делит ли 16 нацело 28? Нет. 28 - 16 = 12.
- Делит ли 12 нацело 16? Нет. 16 - 12 = 4.
- Делит ли 4 нацело 12? Да. Значит, НОД(44, 60) = 4.
Обратите внимание, НОДом является не частное, а делитель. Если в примере мы разделим 12 на 4, то получим частное 3. Но это не НОД.
Доказательство алгоритма Евклида
Примем во внимание факт, что если одно натуральное число из пары нацело делит другое, то их НОД будет равен меньшему из них. Записать это можно так:
если a / b нацело, то НОД(a, b) = b. Например, НОД(15, 5) = 5.
Таким образом, если в конечном итоге мы приходим к паре чисел, одно из которых делит нацело другое, то меньшее будет для обоих наибольшим общим делителем. Именно такая пара чисел ищется алгоритмом Евклида: одно число нацело делит другое.
Второй факт. Требуется доказать, что если одно число больше другого, то их наибольший общий делитель равен наибольшему общему делителю для меньшего числа из пары, и разнице большего и меньшего чисел. Это можно записать так:
если a < b, то НОД(a, b) = НОД(a, b - a).
Доказать, что НОД(a, b) = НОД(a, b - a) можно следующим образом. Пусть b - a = c. Если какое-либо число x делит нацело a и b, то оно будет также делить нацело c. Ведь если a и b различны, то делитель в них укладывается целое, но разное число раз. И если вычесть одно из другого, то делитель также должен укладываться целое число раз в полученную разность.
Если последовательно уменьшать a и b, то рано или поздно придем к такому значению меньшего из них, которое нацело делит большее. Меньшее в такой паре будет наибольшим общим делителем для исходной пары натуральных чисел. В этом и заключается алгоритм Евклида.
scienceland.info
