Главная›Калькуляторы

Калькулятор теории чисел (НОД, НОК)

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

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

Кнопка «По шагам» показывает деления по очереди. Повторное нажатие ставит показ на паузу.

    Результат

    —

    ƒКак получается результатЕвклид, НОК и дерево множителей

    НОД ищется алгоритмом Евклида. Пока второе число не равно нулю, первое делится на второе с остатком, и пара заменяется на делитель и остаток. Последний ненулевой остаток равен НОД. Для 48 и 36 шаги такие: 48 = 1 × 36 + 12, затем 36 = 3 × 12 + 0. НОД = 12.

    НОК(a, b) = a / НОД × b. Деление выполняется первым, поэтому произведение не округляется. Для 48 и 36 НОК = 144. Проверка: 12 × 144 = 48 × 36 = 1728.

    Список множителей собирается пробным делением: сначала на 2, затем на нечётные 3, 5, 7 и дальше, пока квадрат делителя не станет больше остатка. 48 = 2 × 2 × 2 × 2 × 3, 36 = 2 × 2 × 3 × 3. Число простое, если множитель один и равен самому числу. 97 простое, 91 = 7 × 13 и составное. Единица подписана отдельно: 1 не простое и не составное.

    Дерево делит составное число на найденный множитель и частное. Среди 2 и нечётных чисел, чей квадрат не больше исходного, берётся наибольший делитель. Для 48 это 3, первая развилка — 3 и 16. На концах остаются простые 3, 2, 2, 2, 2. Красная обводка отмечает простое, произведение листьев равно 48.

    Делители собираются из этих простых и сортируются. У 36 их девять: 1, 2, 3, 4, 6, 9, 12, 18, 36. Сумма 91, число в середине списка — 6. Если делителей больше 240, на экране остаются первые 240, сумма считается по полному списку.

    Список Фибоначчи начинается с 1, 1. Следующее число — сумма двух предыдущих. В список входят значения, которые не больше N. Число 1 стоит в списке дважды, как первое и второе. Для 10 список такой: 1, 1, 2, 3, 5, 8.

    Принимаются целые от 1 до 1 000 000 000 000. Пустое поле, дробь и отрицательное число не заменяются другим значением: прежний результат при этом снимается.

    Что считает калькулятор

    Пять кнопок задают задачу: НОД и НОК, множители, простота, Фибоначчи, делители. Для НОД и НОК заполняются оба числа. В остальных режимах достаточно числа a, поле b скрывается. Кнопки под полями подставляют примеры: 48 и 36, 17 и 19, 360 и 48, а в других режимах одно число, например 97, 36 или 10.

    Кнопка «По шагам» показывает деления Евклида по очереди. Повторное нажатие ставит показ на паузу. Стрелки влево и вправо листают шаги, когда фокус стоит на блоке алгоритма. Пробелы в записи числа убираются. Принимаются целые от 1 до 1 000 000 000 000. Пустое поле, дробь, ноль и отрицательное число прежний результат снимают, рядом появляется текст ошибки.

    Алгоритм Евклида и НОК

    НОД ищется так: пока второе число не равно нулю, первое делится на второе нацело, запоминаются частное и остаток, пара заменяется на делитель и остаток. Последний ненулевой остаток равен НОД. Для 48 и 36 шаги такие: 48 = 1 × 36 + 12, затем 36 = 3 × 12 + 0. НОД = 12.

    НОК(a, b) = a / НОД × b. Деление выполняется первым, в целых, поэтому произведение не округляется. Для 48 и 36 НОК = 144. Проверка: 12 × 144 = 48 × 36 = 1728. Для 17 и 19 НОД = 1, НОК = 323. Для 360 и 48 НОД = 24, НОК = 720. Красная полоса на схеме — первое число текущего шага, голубая — второе. Когда остаток становится нулём, на схеме остаётся НОД.

    Множители, простота и делители

    Список множителей собирается пробным делением: сначала на 2, затем на нечётные 3, 5, 7 и дальше, пока квадрат делителя не станет больше остатка. 48 = 2 × 2 × 2 × 2 × 3. 36 = 2 × 2 × 3 × 3. У числа 1 этот список пуст. Число простое, если множитель один и он равен самому числу. 97 и 2 простые. 91 = 7 × 13, оно составное. Единица подписана отдельно: 1 не простое и не составное.

    Дерево делит составное число на найденный множитель и частное. Среди 2 и нечётных чисел, чей квадрат не больше исходного, берётся наибольший делитель. Для 48 это 3, первая развилка — 3 и 16. Дальше 16 делится на 2 и 8, 8 на 2 и 4, 4 на 2 и 2. На концах остаются простые 3, 2, 2, 2, 2. Красная обводка отмечает простое. Произведение листьев равно 48: тот же набор, что в строке 2 × 2 × 2 × 2 × 3, в другом порядке.

    Делители собираются из этих простых: перебираются все произведения их степеней и сортируются. Делители 36: 1, 2, 3, 4, 6, 9, 12, 18, 36. Их девять, сумма 91, число в середине списка — 6. Если делителей больше 240, на экране остаются первые 240, а сумма считается по полному списку. В режиме «Простота» рядом проверяются числа на 2 меньше и на 2 больше. Для 97 это 95 и 99, оба не простые.

    Числа Фибоначчи

    Список начинается с 1, 1. Следующее число — сумма двух предыдущих. В список входят значения, которые не больше N. Единица стоит дважды, как первое и второе число. Для N = 10 список такой: 1, 1, 2, 3, 5, 8. Крупное число — 8, в списке шесть значений, 10 в него не входит. Для N = 1 список остаётся 1, 1, и единица в него входит. На верхней границе 1 000 000 000 000 в списке 59 чисел, наибольшее — 956 722 026 041.