Как найти число простых делителей числа

Здравствуйте, дорогие читатели! Как посчитать, сколько делителей у какого-нибудь числа? Если это число маленькое, то никаких сложностей не возникает. Например, для числа 10, мы легко можем найти все делители и посчитать их количество простым перебором. А вот как узнать, на какое количество различных чисел делится, например, число 720? Можно, конечно, опять же перебрать все делители, но это будет довольно трудоемко. При чем, 720 – еще и довольно маленькое число.

Сегодня, я Вам расскажу, как находить количество делителей любого натурального числа, зная всего лишь одну простую формулу.

На самом деле, наша сегодняшняя формула будет даже проще, чем те, которые изображены на картинке выше)

Вы находитесь на канале Trifler, где я разбираю интересные математические задачи, а также рассуждаю на некоторые околоматематические темы. Если Вы искренне увлечены математикой, но еще не подписаны на этот канал, то самое время это исправить! Подписаться

Чудо-формула

Ну что ж, пора переходить от разговоров к делу.

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

Если не совсем понятно, о чем идет речь, то потом посмотрите пример ниже. На самом деле, все очень просто.

Так вот, после того, как мы найдем такое представление числа n, количество его делителей можно будет посчитать по формуле:

Посмотрим, как все это считается на примере

Пример

Раскладываем это число на простые множители, чтобы получить нужное представление:

Теперь, запишем число 720 в каноническом виде:

Ну и все, остается только применить чудо-формулу:

Вот и все, получили, что у числа 720 имеется 30 различных натуральных делителей. Стоит сделать замечание:

По этой формуле мы считаем количество делителей вместе с единицей и самим числом.

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

Читайте также ТОП-3 статьи, выпущенные в этом месяце на моем канале:

1. Quincy: робот, который обучит Ваших детей математике, английскому и рисованию
2. Почему вторая степень это квадрат, а третья – куб
3. Необычное тригонометрическое уравнение

Была ли эта статья полезной?

Каждый школьник знает, что все числа делятся на простые и составные. Более того, тем, кто усердно изучает математику, известны и их свойства. Однако если ответ на вопрос, сколько делителей имеет простое число, скрыт в самом определении этого понятия, то выяснить количество простых делителей для заданного — достаточно сложная задача. Она решается с применением метода перебора и вероятностных алгоритмов, реализуемых на ЭВМ.

Немного истории

Достоверно известно, что серьезным изучением свойств простых чисел первыми стали заниматься древние греки. Однако об их существовании было известно за несколько тысячелетий до того, как Аристотель включил теоремы об их свойствах в свои знаменитые “Начала”. Древние греки придумали и решето Эратосфена, представляющее собой алгоритм нахождения простых чисел из промежутка [1,n].

В 17 веке прорыв в их изучении сделали Пьер Ферма и Марен Мерсенн. Первый сформулировал теорему, впоследствии названную его именем, согласно которой все числа вида 2²ⁿ — простые, доказав ее для n =1..4. Однако впоследствии Леонардом Эйлером было показано, что при n=5 получается составное число. Параллельно с этим Марен Мерсенн выделил простые числа вида 2^p – 1, в которых p – простое. Они интересны тем, что для них легко проверить соответствие критерию простоты. Учитывая этот факт, числа Мерсенна используют для выявления сверхбольших простых чисел. На данный момент предельное из известных выглядит как 2^77232917 − 1 .

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

Большую роль в исследовании простых чисел сыграли также Лежандр и Гаусс. Эти ученые выдвинули гипотезу об их плотности.

Решето Эратосфена

Если можно сразу же назвать простые делители числа 4, то для больших чисел сделать это обычно достаточно затруднительно. О решении этой проблемы люди стали задумываться еще несколько тысячелетий назад. В частности, древнегреческий математик Эратосфен, живший на стыке третьего и второго веков до Рождества Христова придумал алгоритм нахождения всех простых чисел, меньших целого числа n.

Он получил название решета, так как «просеивает» или по-современному «фильтрует» все числа, кроме простых.

Алгоритм состоит из следующих команд:

1. выписать все целые числа от 2 до n;
2. присвоить переменной p значение 2, так как это наименьшее простое число;
3. зачеркнуть в списке все числа от 2p до n, кратные p;
4. присвоить значению переменной p значение первого, не зачеркнутого числа записанной последовательности, которое большее p;
5. повторять 3-й и 4-й, пока возможно.

Если все сделано правильно, то в списке останутся не зачеркнутыми все простые числа от двух до n.

Для реализации решета Эратосфена на электронно-вычислительной машине используют модернизированный алгоритм. На 3-м шаге можно зачеркивать числа, начиная с числа p₂, так как все составные числа, которые меньше него, к этому времени уже будут зачеркнуты. Тогда остановка работы алгоритма должна произойти, когда выполнится условие p₂>n.

Следует также учесть, что все простые числа, за исключением двойки, — нечетные, поэтому, начиная с p2 можно «фильтровать» по 2p.

Основная теорема арифметики

Согласно определению, простое число имеет два делителя. Один из них — 1, а второй — сама эта величина.

Прежде чем выяснить, каково число простых делителей числа, стоит уделить немного времени изучению основной теоремы арифметики. Согласно ей, натуральное число n > 1 можно представить, как n = p₁*… ⋅*p_k, где p₁, … , p_m — простые числа. При этом такое представление является единственным с точностью до порядка следования его сомножителей.

Следствие этой теоремы можно сформулировать следующим образом: любое натуральное число n представимо в виде n = p₁ ^d1*p₂^d2 * …* p_k^dm (в другой формулировке: каноническое разложение числа n на простые сомножители имеет вид n = p₁ ^d1*p₂^d2*⋅ …⋅*p_k^dm), где p₁<p₂< … <p_m — простые числа, и d₁, … , d_m— некоторые натуральные числа.

Кроме того, уже известную вам основную теорему арифметики можно перефразировать следующим образом: любое каноническое разложение n можно считать тождественным, если не обращать внимания на порядок делителей. Это значит, что на практике для значительной части чисел существует множество достаточно простых алгоритмов их разложения на простые множители, которые в итоге дают один и тот же результат.

Критерий простоты

Прежде чем выяснить, как можно найти наибольший простой делитель числа (НПД) n, следует разобраться с другим важным вопросом.

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

Сделать это можно путем перебора простых чисел p₁, …p_k. Причем завершить цикл можно, как только p_i+1, для которого производилась проверка, будет удовлетворять условию (pi₊₁)²> n.

Дадим объяснение, почему перебор можно ограничить p_i>=sqr(n).

Предположим, у числа n, исследуемого на простоту есть некоторый делитель p. Тогда d=n/p так же будет его делителем. Но, так как d и p — разные числа, ни один из них не может быть больше корня из n.

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

Найти НПД n, можно, действуя по следующей схеме:

• Разделить n на два, если оно четное или на три, если нечетное. Исключение составляет n, последняя цифра в десятичной записи которого ноль или пять. Такое число можно сразу разделить на пять.
• Если результат не целое число, то делят n на следующие целые числа, перебирая их вплоть до p_i>=sqr(n).

Над получившимся числом n₁ производят все действия, в том же порядке, что представлен выше, только с условием p_i>=sqr(n₁).

Если же ни на одном из шагов перебора n₁ не делится на одно из простых чисел, то n целое и является своим же НПД. В противном случае получаем n₂ и продолжаем деление с перебором до момента, когда на (i+1) шаге установим, что n_i — целое.

Пример

Найдем простые делители числа 276.

• делим на “два”;
• получаем 138;
• так как число четное, то вновь делим на “два”;
• результат — 69;
• делим на следующее простое число “три”;
• получаем 23.

Так как это число простое, можем подвести итог. Простыми делителями 276 являются 2, 3 и 23.

Как найти число простых делителей числа

Если речь идет о целом малом числе, то решение такой задачи не представляет никакой сложности. Рассмотрим конкретный пример. Найдем простые делители числа 54.

Для этого:

• 54 делим на “два” и получаем 27;
• 27 нечетное, поэтому разделим его уже не на “два”, а на следующее простое число, т. е. “три”;
• заметим, что 27=3³;
• таким образом, разложение 54 имеет вид 54 = 2¹ * 3³, т.е. простые делители числа 54 — это “два” и “три”.

Однако это не все, что мы хотели знать. Теперь найдем число простых делителей числа 54. Оно равно произведению степеней простых множителей канонического разложения числа n = p₁*^d1 p₂^d2*⋅ …⋅*p_m^dm, увеличенных на 1. Иными словами, в общем случае K = (d₁+1)*…* (d_m+1).

Тогда для 54 имеем К = 2 * 4 = 8, т. е. общее число делителей равно восьми.

Обратите внимание, что все значительно упростилось, если бы речь шла о 23, 37, 103 и пр., так как каждый знает, сколько делителей у простого числа.

Пример

Найти число простых делителей числа 9990.

• так как число 9990 заканчивается на цифру “ноль”, то оно делится на пять и на два.
• имеем 999.
• в результате деления на три имеем 333;
• снова делим на три, получаем 111;
• делим на три, имеем 37;
• 37 простое число, так как не делится без остатка ни на одно из простых чисел, которые находятся между двойкой и корнем из числа 37;
• подсчитываем количество простых делителей числа 9990. Это 2,3,5 и 37, то есть всего их четыре.

Проблема больших чисел

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

Простые числа и защита информации

Каждый современный человек, который пользуется возможностями, которые возникли благодаря появлению локальных компьютерных сетей и Интернета, нуждается в защите конфиденциальности своих личных данных, электронной переписки и пр. С этой целью используются криптографические алгоритмы с открытым ключом.

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

Для этой цели наиболее распространенные на данный момент алгоритмы RSA используют большие простые числа.

Существует всего 10151 простых чисел длиною 1 – 512 битов включительно. В то же время для чисел, которые близки к n, вероятность того факта, что случайно выбранное число будет простым, — 1/ln n. Таким образом, полное количество простых чисел, которые меньше n равно n/ln n. Это позволяет считать, что крайне маловероятно, что 2 человека выберут одно и то же большое простое число.

Тест Миллера — Рабина

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

Тест Миллера—Рабина основан на проверке ряда условий, выполняемых для чисел, которые делятся только на 1 и на самих себя. Если хотя бы одно из требований нарушено, это «экзаменуемое» число признается составным.

Для данного m находятся целые нечетное число t и s, такие чтобы выполнялось условие m-1=2^st.

Затем выбирается случайное число a, такое что 1<a<m. Если a не свидетельствует о простоте числа m, то программа должна выдать ответ «m составное» и завершить свою работу. В противном случае выбирается другое случайное число a и проверка повторяется снова. После того как будут установлены r свидетелей простоты, должен быть выдан ответ «m, вероятно, простое», и алгоритм завершит свою работу.

Следствием теоремы Рабина является тот факт, что если r чисел, которые выбраны случайно, признаны свидетелями для определения простоты числа m, то вероятность того, что оно составное, не может превосходить (4^-r).

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

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

Как найти все делители числа

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

Если речь идет о простом числе, то его можно разделить только на единицу и на само себя. Значит, у любого простого числа a есть всего 4 делителя, два из которых больше 0 и два меньше: 1, -1, a, -a. Возьмем простое число 7: у него есть делители 7, -7, 1 и -1, и все. Еще один пример: 367 – тоже простое число, которое можно разделить лишь на 1, -1, 367 и -367.

Сложнее определить все делители составного числа. Сформулируем теорему, которая лежит в основе данного действия.

Допустим, у нас есть выражение, означающее каноническое разложение числа на простые множители, вида a=p1s1·p2s2·…·pnsn. Тогда натуральными делителями числа a будут следующие числа: d=p1t2·p2t2·…·pntn, где t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.

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

Для этого нужно выполнить следующие действия:

1. Выполнить каноническое разложение на простые множители и получить выражение вида a=p1s1·p2s2·…·pnsn.
2. Найти все значения d=p1t2·p2t2·…·pntn, где числа t1, t2, …, tn будут принимать независимо друг от друга каждое из значений t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.

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

Возьмем пример чуть сложнее: в нем при разложении числа получится не один, а два множителя.

Продолжим усложнять наши примеры – возьмем четырехзначное число.

Как определить количество делителей конкретного числа

Чтобы узнать, сколько положительных делителей у конкретного числа a, каноническое разложение которого выглядит как a=p1s1·p2s2·…·pnsn, нужно найти значение выражения (s1+1) ·(s2+1) ·…·(sn+1). О количестве наборов переменных t1, t2, …, tn мы можем судить по величине записанного выражения.

Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа 3 900, которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: 3 900=22·3·52·13. Значит, s1=2, s2=1, s3=2, s4=1. Теперь подставим значения s1, s2, s3 и s4 в выражение (s1+1) ·(s2+1) ·(s3+1) ·(s4+1) и вычислим его значение. Имеем (2+1)·(1+1)·(2+1)·(1+1)=3·2·3·2=36. Значит, это число имеет всего 36 делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет 72 делителя.

Как вычислить общие делители нескольких чисел

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

Разберем пару таких задач.