Что значит имеющих делителями числа

Нахождение всех делителей числа, число делителей числа.

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

Навигация по странице.

Все делители числа, их нахождение

Дальнейшее изложение подразумевает хорошее владение информацией статьи делители и кратные числа. Мы будем говорить лишь о поиске всех делителей целых положительных чисел (натуральных чисел). Этого вполне достаточно, так как одно из свойств делимости утверждает, что множество делителей целого отрицательного числа −a совпадает со множеством делителей противоположного числа a (которое будет положительным). Напомним также, что число 0 имеет бесконечно много делителей, и нахождение всех делителей нуля не представляет интереса.

положительными делителями простого числа a являются лишь единица и само это число. Следовательно, любое простое число a имеет четыре делителя, среди которых два положительных и два отрицательных: 1 , −1 , a и −a . Например, число 11 – простое, оно имеет всего четыре делителя 1 , −1 , 11 и −11 . Еще пример. Число 367 тоже простое, все его делители – это числа 1 , −1 , 367 и −367 .

Читайте также:  Что значит подмножество множеств

Интереснее проходит поиск всех делителей составных чисел. Теоретическая основа этого процесса заключается в следующей теореме.

С одной стороны, по определению делимости число a делится на любое такое число d , так как существует такое целое число q=p1 (s1−t1) ·p2 (s2−t2) ·…·pn (sn−tn) , что a=d·q .

С другой стороны, всякое число d , которое делит a , имеет указанный вид, так как в силу свойств делимости оно не может иметь других простых множителей, кроме p1, p2, …, pn , а показатели этих множителей не могут превышать s1, s2, …, sn соответственно.

Из рассмотренной теоремы следует алгоритм нахождения всех положительных делителей данного числа. Чтобы найти все делители числа a нужно:

  • получить его каноническое разложение на простые множители вида a=p1 s1 ·p2 s2 ·…·pn sn ;
  • вычислить все значения выражения p1 t1 ·p2 t2 ·…·pn tn , в которых числа t1, t2, …, tn принимают независимо друг от друга каждое из значений t1=0, 1, …, s1 , t2=0, 1, …, s2 , …, tn=0, 1, …, sn .

Обычно наибольшую трудность представляет именно процесс перебора всех возможных комбинаций значений чисел t1, t2, …, tn . Сейчас мы последовательно рассмотрим решения нескольких примеров нахождения всех делителей чисел, откуда будут понятны все тонкости этого процесса.

Найдите все делители числа 8 .

Получить разложение на простые множители числа 8 не составляет труда: 8=2·2·2 . В канонической форме это разложение выглядит так: 8=2 3 . То есть, в нашем случае a=8 , p1=2 , s1=3 .

Тогда все делители числа 8 представляют собой значения выражения p1 t1 =2 t1 , в котором t1 принимает значения 0 , 1 , 2 и 3 ( 3 – последнее значение, так как s1=3 ). Итак, при t1=0 имеем 2 t1 =2 0 =1 , при t1=1 имеем 2 t1 =2 1 =2 , при t1=2 имеем 2 t1 =2 2 =4 , наконец, при t1=3 имеем 2 t1 =2 3 =8 .

Весь процесс нахождения делителей удобно проводить, заполняя таблицу следующего вида:

Таким образом, 1 , 2 , 4 и 8 – это все положительные делители числа 8 . Отрицательными делителями числа 8 являются −1 , −2 , −4 и −8 .

±1 , ±2 , ±4 , ±8 – все делители числа 8 .

Рассмотрим более сложный пример нахождения всех делителей числа a , в нем разложение числа уже будет содержать два простых множителя.

Перечислите все натуральные делители числа 567 .

Сначала разложим на простые множители число 567 :

Каноническое разложение числа 567 на простые множители имеет вид 567=3 4 ·7 . Теперь для нахождения всех натуральных делителей числа 567 заставим t1 и t2 пробегать независимо друг от друга значения 0 , 1 , 2 , 3 , 4 и 0 , 1 соответственно, при этом будем вычислять значения выражения 3 t1 ·7 t2 . Все эти действия удобно поводить, заполняя следующую таблицу:

1 , 3 , 7 , 9 , 21 , 27 , 63 , 81 , 189 и 567 – все натуральные делители числа 567 .

Еще немного усложним пример.

Найдите все положительные делители числа 3 900 .

Разложив число 3 900 на простые множители, получим его каноническое разложение 3 900=2 2 ·3·5 2 ·13 . Все положительные делители найдем, вычисляя значения выражения 2 t1 ·3 t2 ·5 t3 ·13 t4 при t1=0, 1, 2 , t2=0, 1 , t3=0, 1, 2 , t4=0, 1 .


1 , 2 , 3 , 4 , 5 , 6 , 10 , 12 , 13 , 15 , 20 , 25 , 26 , 30 , 39 , 50 , 52 , 60 , 65 , 75 , 78 , 100 , 130 , 150 , 156 , 195 , 260 , 300 , 325 , 390 , 650 , 780 , 975 , 1 300 , 1 950 , 3 900 — все положительные делители числа 117 000 .

Число делителей числа

Число положительных делителей данного числа a , каноническое разложение которого имеет вид a=p1 s1 ·p2 s2 ·…·pn sn , равно значению выражения (s1+1)·(s2+1)·…·(sn+1) . Величина записанного выражения дает количество всех возможных наборов переменных t1, t2, …, tn , где t1=0, 1, …, s1 , t2=0, 1, …, s2 , …, tn=0, 1, …, sn .

Приведем пример. Вычислим число натуральных делителей числа 3 900 из последнего примера, рассмотренного в предыдущем пункте. Мы выяснили, что 3 900=2 2 ·3·5 2 ·13 , тогда s1=2 , s2=1 , s3=2 , s4=1 . Осталось вычислить значение выражения (s1+1)·(s2+1)·(s3+1)·(s4+1) при данных значениях s1 , s2 , s3 и s4 , которое и даст нам искомое число натуральных делителей. Получаем (2+1)·(1+1)·(2+1)·(1+1)=3·2·3·2=36 . Следовательно, число 3 900 имеет 36 натуральных делителей. Если мы пересчитаем все делители числа 3 900 , полученные в предыдущем примере, то убедимся, что их количество действительно равно 36 . Число всех делителей (и положительных и отрицательных) числа 3 900 равно 36·2=72 , так как число 3 900 имеет 36 положительных делителей, и, следовательно, 36 отрицательных, противоположных каждому из положительных делителей.

Найдите число делителей числа 84 .

Разложим 84 на простые множители:

Таким образом, каноническое разложение имеет вид 84=2 2 ·3·7 . Тогда число положительных делителей равно (2+1)·(1+1)·(1+1)=12 . Следовательно, число всех делителей равно 2·12=24 .

число 84 имеет 24 делителя.

Нахождение всех общих делителей чисел и их количества

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

Рассмотрим решения примеров, в которых находятся все общие делители некоторых чисел.

Найдите все натуральные общие делители чисел 50 и 140 , а также их количество.

Сначала нам нужно найти наибольший общий делитель чисел 50 и 140 , для этого воспользуемся алгоритмом Евклида: 140=50·2+40 , 50=40·1+10 , 40=10·4 , то есть, НОД(50, 140)=10 .

Теперь определим все положительные делители числа 10 . Его разложение на простые множители имеет вид 10=2·5 . Тогда 2 0 ·5 0 =1 , 2 0 ·5 1 =5 , 2 1 ·5 0 =2 и 2 1 ·5 1 =10 – все делители числа 10 . Следовательно, числа 1 , 2 , 5 и 10 – это все положительные общие делители чисел 50 и 140 , количество этих делителей равно 4 .

1 , 2 , 5 и 10 – это все натуральные делители чисел 50 и 140 , их количество равно 4 .

Определите число всех положительных общих делителей четырех чисел 90 , 45 , 315 и 585 .

Сначала найдем НОД с помощью разложения чисел на простые множители. Так как 90=2·3·3·5 , 45=3·3·5 , 315=3·3·5·7 и 585=3·3·5·13 , то НОД(90, 45, 315, 585)=3·3·5=3 2 ·5 . Количество всех искомых положительных общих делителей исходных четырех чисел равно количеству всех положительных делителей НОД этих чисел. Вычислим количество делителей НОД(90, 45, 315, 585)=3 2 ·5 , оно равно (2+1)·(1+1)=6 .

Источник

Нахождение всех делителей числа

Все делители числа

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

Нахождение всех делителей числа выполняется следующим образом:

  1. Сначала нужно разложить данное число на простые множители.
  2. Выписываем каждый полученный простой множитель (без повторов, если какой-то множитель повторяется).
  3. Далее, находим всевозможные произведения всех полученных простых множителей между собой и добавляем их к выписанным простым множителям.
  4. В конце добавляем в качестве делителя единицу.

Например, найдём все делители числа 40. Раскладываем число 40 на простые множители:

40
20
10
5
1
2
2
2
5

Выписываем (без повторов) каждый полученный простой множитель — это 2 и 5.

Далее находим всевозможные произведения всех полученных простых множителей между собой:

2 · 2 = 4,
2 · 2 · 2 = 8,
2 · 5 = 10,
2 · 2 · 5 = 20,
2 · 2 · 2 · 5 = 40.

Добавляем в качестве делителя 1. В итоге получаем все делители, на которые число 40 делится без остатка:

1, 2, 4, 5, 8, 10, 20, 40.

Других делителей у числа 40 нет.

Калькулятор нахождения всех делителей

Данный калькулятор поможет вам получить все делители числа. Просто введите число и нажмите кнопку «Вычислить».

Источник

Число простых делителей числа. Сколько делителей имеет простое число?

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

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

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

В 17 веке прорыв в их изучении сделали Пьер Ферма и Марен Мерсенн. Первый сформулировал теорему, впоследствии названную его именем, согласно которой все числа вида 2 2n — простые, доказав ее для 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-м шаге можно зачеркивать числа, начиная с числа p2, так как все составные числа, которые меньше него, к этому времени уже будут зачеркнуты. Тогда остановка работы алгоритма должна произойти, когда выполнится условие p2>n.

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

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

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

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

Следствие этой теоремы можно сформулировать следующим образом: любое натуральное число n представимо в виде n = p1 d1 *p2 d2 * …* pk d m (в другой формулировке: каноническое разложение числа n на простые сомножители имеет вид n = p1 d1 *p2 d2 *⋅ …⋅*pk d m ), где p1

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

Однако это не все, что мы хотели знать. Теперь найдем число простых делителей числа 54. Оно равно произведению степеней простых множителей канонического разложения числа n = p1* d1 p2 d2 *⋅ …⋅*pm d m , увеличенных на 1. Иными словами, в общем случае K = (d1+1)*. * (dm+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 s t.

Затем выбирается случайное число a, такое что 1

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

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

Источник

Оцените статью