Калькулятор делителей числа

60 ÷ 1 = 60 ⇒ 1 * 60; 60 ÷ 2 = 30 ⇒ 2 * 30; 60 ÷ 3 = 20 ⇒ 3 * 20; 60 ÷ 4 = 15 ⇒ 4 * 15; 60 ÷ 5 = 12 ⇒ 5 * 12; 60 ÷ 6 = 10 ⇒ 6 * 10; 60 ÷ 7 нацело не делится, 8 × 8 > 60, стоп

n

Число, которое раскладывают на делители, — целое от 1 до 1 000 000. Единица допускается и даёт единственный делитель, 1: это настоящий ответ, а не вырожденный случай — единица делится сама на себя и не делит нацело ничего, кроме своих кратных

d

Пробный делитель, проверяемый по порядку: 1, 2, 3, 4 и так далее. Страница никогда не заходит дальше квадратного корня из n, и в этом весь фокус: если d × e = n и d больше корня, то e меньше него, значит e уже найдено и пара уже напечатана

d * d ≤ n

Условие остановки, записанное явно. Для 60 последний проверяемый делитель — 7, потому что 7 × 7 = 49 меньше 60, а 8 × 8 = 64 уже больше. Из-за этого правила число проверок растёт как квадратный корень из ввода, а не как сам ввод: миллион требует тысячи проб, а не миллиона

n / d

Партнёр делителя. Когда d делит n нацело, частное и есть вторая половина пары, и страница выдаёт её тем же шагом. Поэтому пары для 60 выходят как 1 * 60, 2 * 30, 3 * 20 и далее по порядку, без сортировки: меньшие половины находятся по возрастанию, а значит и пары тоже

1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Все делители числа 60 одним плоским списком, по возрастанию. Двенадцать штук — чётное число: разбиение на пары полное, у каждого делителя есть партнёр. Это ровно та же информация, что и в парах ниже, только разложенная: прочитайте пары и соберите числа — получите эту строку обратно

6 * 6

Средняя пара числа 36 и единственная форма, в которой делитель встречается в одной строке дважды. 36 — полный квадрат, поэтому делителей у него нечётное число: 1, 2, 3, 4, 6, 9, 12, 18, 36, то есть девять, и страница печатает среднюю пару один раз, а не дважды. Вот почему у полного квадрата число делителей никогда не бывает чётным

Сокращение дроби — самая частая причина искать список делителей. Чтобы вручную сократить 42/60, вы ищете число, на которое делятся оба: делители 60 подсказывают кандидатов, а делители 42 — какие из них подходят; наибольший из подходящих и есть наибольший общий делитель, и если нужен только он, на этот вопрос прямо отвечает отдельная страница про НОД. Второе применение — прямоугольник с заданной площадью: грядка в 60 квадратных метров может быть 1 на 60, 2 на 30, 3 на 20, 4 на 15, 5 на 12 или 6 на 10, и пары множителей — это ровно список возможных форм, поэтому они и печатаются в таком виде. Тот же вопрос возникает всюду, где предметы надо расставить равными рядами и столбцами: рассадить 60 гостей за столы одинакового размера или разбить класс на группы равной численности, чтобы никто не остался лишним. Третье применение — проверка утверждения. Если кто-то говорит, что 91 — простое число, список его делителей закрывает вопрос: 1, 7, 13, 91, и то, что строк четыре, а не две, и есть опровержение. Признаки делимости на 2, 3, 5 и 9 покрывают мелкие случаи вручную, а эта страница подхватывает там, где они перестают быть удобными. Когда вопрос на самом деле не о делителях, а о кусочках, ответ живёт в другом месте: разложение на простые множители делает отдельная страница про простые множители, а сравнивают два числа между собой, а не описывают одно, страницы про НОК и НОД; сократить дробь сразу, не показывая список, умеет страница про сокращение дробей.

1. Двенадцать делителей: 60

   1. Проба 1: 60 ÷ 1 = 60 нацело, значит и 1, и 60 — делители
   2. Проба 2: 60 ÷ 2 = 30, значит 2 и 30 — делители; проба 3: 60 ÷ 3 = 20, это 3 и 20
   3. Проба 4: 60 ÷ 4 = 15, это 4 и 15; проба 5: 60 ÷ 5 = 12, это 5 и 12
   4. Проба 6: 60 ÷ 6 = 10, это 6 и 10; проба 7: 60 ÷ 7 нацело не делится
   5. 8 × 8 = 64 уже больше 60, значит пора остановиться — двенадцать делителей собраны полностью

   Ввод по умолчанию, и удачный: у 60 делителей много — двенадцать, больше, чем у любого числа до него. Обратите внимание, насколько дешёвым оказался поиск: семь проб вместо шестидесяти. Строка пар и список делителей — это одни и те же двенадцать чисел; пары просто сложены так, что каждое стоит рядом с тем, на что умножается. Стоит заметить и то, что список пар заканчивается на 6 * 10, а не продолжается на 10 * 6: как только меньшая половина пары переходит через квадратный корень, каждая оставшаяся пара повторяет уже напечатанную.

2. Полный квадрат: 36

   1. 1 и 36 образуют пару, затем 2 и 18, затем 3 и 12, затем 4 и 9
   2. 6 × 6 = 36, значит 6 — партнёр самому себе, это середина списка
   3. 7 не делит 36; 7 × 7 = 49 уже больше, но 6 был последним делителем под квадратным корнем
   4. Делители: 1, 2, 3, 4, 6, 9, 12, 18, 36 — девять штук, нечётное число

   Случай, который объясняет, почему число делителей вообще может быть нечётным. У каждого делителя, кроме квадратного корня, есть отдельный партнёр, поэтому они разбиваются на пары и дают чётный вклад; квадратный корень оказывается партнёром самому себе и добавляет единицу. Отсюда и вся разница: у 36 делителей девять, а у 60, числа большего, — двенадцать; у 12 — шесть. В строке пар 6 * 6 напечатано один раз, а не дважды, и это решение: напечатай страница дважды, две строки начали бы расходиться в том, сколько всего делителей.

3. Простое число: 7

   1. Проба 1: 7 ÷ 1 = 7 нацело, значит 1 и 7 — делители
   2. Проба 2: 7 ÷ 2 нацело не делится; 3 × 3 = 9 уже больше 7, значит поиск здесь и заканчивается
   3. Ничто между 1 и 7 на 7 не делится
   4. Два делителя и одна пара — это и есть определение простого числа

   Самый короткий нетривиальный результат на странице и тот случай, который показывает: простое число — не неудача перебора. У простого числа ровно два делителя, и это всегда 1 и само число; страница сообщает этот факт, а не жалуется, что ничего не нашла. Условие остановки здесь работает по-настоящему: после проверки двойки проверять уже нечего, потому что 3 × 3 больше 7. Пробы 3, 4, 5 и 6 стоили бы четырёх делений и не могли бы ничего найти.

Ввод должен быть целым числом от 1 до 1 000 000. Ноль отклоняется: на ноль делится любое целое число, поэтому список его делителей был бы бесконечным и печатать в нём было бы нечего. Отрицательные числа тоже отклоняются, хотя ±1, ±2 и так далее делят −60: страница сообщает положительные делители положительного числа, а для списка со знаками понадобилось бы соглашение о том, показывать ли оба знака, которого эта страница нигде не формулирует. Дробные числа отклоняются, а не округляются. Потолок в миллион ограничивает перебор: поиск останавливается на квадратном корне, поэтому в худшем случае это тысяча проб, и список ответов может быть длинным, но не безразмерным. Длинным он всё же бывает: у 720 720 делителей 240 — больше, чем у любого числа до миллиона, — и такой список верен, но читать его не слишком приятно. Далее, страница сообщает делители и пары множителей, а не простые множители, и разницу легко не заметить: в списке делителей 60 присутствуют 2, 3 и 5, но страница нигде не говорит, что 60 = 2² × 3 × 5, а для большого числа эти два вопроса стоят совершенно по-разному. Признаки делимости на 2, 3, 5 и 9 отдельно не выделяются — они просто растворяются в переборе, так что число, оканчивающееся на ноль, покажет 2, 5 и 10 в делителях без всякого объяснения почему. Каждый делитель печатается целым числом в списке через запятую, а в парах для умножения стоит звёздочка; разделителей разрядов в выводе нет, поэтому делитель-миллион печатается как 1000000 — обратите внимание, что в тексте этой страницы то же число записано как 1 000 000, и это не противоречие: панель выводит строку как есть, а проза следует правилам языка. Наконец, таблица ниже показывает три фиксированных числа, а не следует за вашим вводом; отвечает на введённое число панель выше.

Чем делитель отличается от множителя?

В этой теме это почти одно и то же, и различаются они только чтением. Делитель — число, на которое делят: 5 — делитель 60, потому что 60 делится на 5 нацело. Множитель — число, которое умножают: в записи 5 × 12 = 60 оба числа множители. Один и тот же делитель всегда можно прочитать как множитель, потому что 60 ÷ 5 = 12 и 5 × 12 = 60 — это одно утверждение, только с разных сторон. Поэтому список делителей и пары множителей на этой странице содержат одни и те же числа, свёрнутые по-разному.

Почему у простого числа всего два делителя?

Потому что так оно и определяется: простое число — то, у которого делителей ровно два, единица и оно само. Для 7 список выглядит как 1, 7, а пар всего одна — 1 * 7. Это не неудача перебора и не особый случай в коде: цикл просто не находит между единицей и самим числом ничего, на что оно делилось бы нацело. И наоборот: если делителей оказалось четыре, как у 91 (1, 7, 13, 91), то число составное, и список это доказывает.

Почему у полного квадрата делителей нечётное число?

Потому что его средняя пара — это одно число дважды. Все остальные делители разбиваются на пары с разными половинами и дают чётный вклад, а квадратный корень оказывается партнёром самому себе и добавляет единицу. У 36 это 6 * 6, и страница печатает такую пару один раз: если напечатать её дважды, две строки начали бы расходиться в том, сколько всего делителей. Отсюда и правило: нечётное число делителей бывает только у полного квадрата.

Почему поиск останавливается на квадратном корне?

Потому что дальше искать нечего. Если d × e = n и при этом d больше квадратного корня из n, то e меньше него, а значит e уже было найдено, и пара с ним уже напечатана. Для 60 это означает семь проб вместо пятидесяти девяти, а для миллиона — тысячу вместо миллиона: число проб растёт как корень из ввода. Именно это правило делает страницу быстрой и оно же объясняет, почему пары выходят уже упорядоченными.

Показывает ли страница разложение на простые множители?

Нет, и разницу легко не заметить. В списке делителей 60 есть 2, 3 и 5, но страница нигде не говорит, что 60 = 2² × 3 × 5. Список делителей содержит кусочки разложения, но сам разложением не является. Практическая разница велика: объём работы здесь растёт как квадратный корень из числа, тогда как разложение на простые множители — задача по-настоящему трудная, и на ней держится вся современная криптография. Если нужны именно простые множители, это отдельный вопрос и отдельная страница.

Почему в выводе нет разделителей разрядов?

Потому что оба вывода — текстовые строки, и панель печатает их ровно в том виде, в каком их собрала программа: делитель-миллион выглядит как 1000000, а не как 1 000 000. Такова особенность именно этой страницы: её ответ — список, длина которого зависит от ввода, а числовой вывод потребовал бы фиксированного числа знаков после запятой, что для списка бессмысленно. В тексте самой страницы то же число записано по правилам русского языка — 1 000 000, — и это не противоречие: проза и машинная строка живут по разным правилам.

• Divisor — what it means for one whole number to divide another exactly, and the convention that every number divides itself — Wolfram MathWorld (United States)
• Prime Number — numbers with exactly two factors, and why that definition is the one the factor list makes visible — Wolfram MathWorld (United States)
• Perfect Square — numbers whose square root is a whole number, and the reason their factor count is always odd — Wolfram MathWorld (United States)