Простой делитель. Простые делители числа


Разложение числа на простые множители онлайн

Любое натуральное число можно представить в виде произведения простых чисел. Это представление называется разложением числа на простые множители.

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

Простым числом называют натуральное число , делящееся только на себя и на единицу. Составным числом называют число, имеющее больше двух различных делителей (любое натуральное число не равное имеет как минимум два делителя: и ). Например, числа – простые, а числа – составные.

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

Данная программа раскладывает число в произведение простых множителей онлайн. Разложить число на множители онлайн с её помощью очень просто.

Как разложить число на множители?

В школе на уроках математики разложение числа на множители обычно записывают столбиком (в две колонки). Делается это так: в левую колонку выписываем исходное число, затем

  • Берём самое маленькое простое число — 2 и по признакам делимости или обычным делением проверяем, делится ли исходное число на 2.
  • Если делится, то в правую колонку выписываем 2. Далее делим исходное число на 2 и записываем результат в левую колонку под исходным числом.
  • Если не делится, то берём следующее простое число — 3.

Повторяем эти шаги, при этом работаем уже с последним числом в левой колонке и с текущим простым числом. Разложение заканчивается, когда в левой колонке будет записано число 1.

Чтобы лучше понять алгоритм, разберём несколько примеров.

Пример. Разложить на множители число 84.

Решение. Записываем число 84 в левую колонку:

Берём первое простое число — два и проверяем, делится ли 84 на 2. Так как 84 оканчивается на 4, а 4 делится на 2, то и 84 делится на 2 по признаку делимости. Записываем 2 в правую колонку. 84:2 = 42, число 42 записываем в левую колонку. Получили вот что:

Теперь работаем уже с числом 42. Число 42 делится на 2, поэтому записываем 2 в правую колонку, 42:2 = 21, число 21 записываем в левую колонку.

Число 21 на 2 не делится, поэтому проверяем его делимость на следующее простое число — 3. Число 21 делится на 3, 21:3 = 7. Записали 3 в правую колонку, 7 — в левую. Получили

Число 7 — простое число, поэтому в правой колонке записываем 7, в левую пишем 1. В итоге получили:

Всё, число разложено!

В результате в правой колонке оказались записаны все простые множители числа 84. То есть 84=2∙2∙3∙7.

О калькуляторе

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

umath.ru

Простой делитель Википедия

Это изображение демонстрирует нахождение простых множителей числа 864. Сокращённый способ написания — 25 × 33

В теории чисел, простые множители (простые делители) положительного целого числа — это простые числа, которые делят это число нацело (без остатка)[1]. Выделить простые множители положительного целого числа означает перечислить эти простые множители вместе с их кратностями. Процесс определения простых множителей называется факторизацией целых чисел. Основная теорема арифметики утверждает, что любое натуральное число можно представить в виде единственного (с точностью до порядка следования) произведения простых множителей[2].

Чтобы сократить выражение, простые множители часто представляются в виде степеней простых чисел (кратностей). Например,

360=2×2×2×3×3×5=23×32×5{\displaystyle 360=2\times 2\times 2\times 3\times 3\times 5=2^{3}\times 3^{2}\times 5}

в котором множители 2, 3 и 5 имеют кратности 3, 2 и 1, соответственно.

Для простого множителя р числа n кратность числа p — это наибольший из показателей степени а, для которых ра делит n нацело.

Для положительного целого числа n, количество простых множителей n и сумма простых множителей n (без учёта кратности) — это примеры арифметических функций из n (аддитивных арифметических функций)[3].

Полный квадрат

Квадрат числа имеет то свойство, что все его простые множители имеют чётные кратности. Например, число 144 (квадрат 12) имеет простые множители

144=2×2×2×2×3×3=24×32.{\displaystyle 144=2\times 2\times 2\times 2\times 3\times 3=2^{4}\times 3^{2}.}

В более понятной форме:

144=2×2×2×2×3×3=(2×2×3)×(2×2×3)=(2×2×3)2=(12)2.{\displaystyle 144=2\times 2\times 2\times 2\times 3\times 3=(2\times 2\times 3)\times (2\times 2\times 3)=(2\times 2\times 3)^{2}=(12)^{2}.}

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

Взаимно простые числа

Положительные целые числа, не имеющие общих простых множителей, называются взаимно простыми. Два целых числа a и b можно назвать взаимно простыми, если их наибольший общий делитель НОД(a, b) = 1. Если для двух целых чисел неизвестны их простые множители, то для определения того, являются ли они взаимно простыми, используется алгоритм Евклида; алгоритм выполняется за полиномиальное время по количеству цифр.

Целое число 1 является взаимно простым для любого положительного целого числа, включая само себя. Иными словами, число 1 не имеет простых множителей, оно — empty product. Это означает, что НОД(1, b) = 1 для любого b ≥ 1.

Криптографические приложения

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

Функции Омега

Функция ω(n) (омега) представляет собой число различных простых множителей n, в то время как функция Ω(n) (большая Омега) представляет собой число простых множителей n, пересчитанное с учётом кратности[2]. Если

n=∏i=1ω(n)piαi,{\displaystyle n=\prod _{i=1}^{\omega (n)}p_{i}^{\alpha _{i}},}

тогда

Ω(n)=∑i=1ω(n)αi.{\displaystyle \Omega (n)=\sum _{i=1}^{\omega (n)}\alpha _{i}.}

Например, 24 = 23 × 31, Так что ω(24) = 2 и Ω(24) = 3 + 1 = 4.

  • ω(n) для n = 1, 2, 3, … соответственно 0, 1, 1, 1, 1, 2, 1, 1, 1, … — последовательность A001221 в OEIS.
  • Ω(n) для n = 1, 2, 3, … соответственно 0, 1, 1, 2, 1, 2, 1, 3, 2, … — последовательность A001222 в OEIS.

См. также

Ссылки

  1. ↑ Jensen, Gary R. Arithmetic for Teachers: With Applications and Topics from Geometry. — American Mathematical Society, 2004.
  2. ↑ 1 2 Riesel, Hans (1994), Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, ISBN 978-0-8176-3743-9 
  3. ↑ Melvyn B. Nathanson. Additive Number Theory: the Classical Bases. — Springer-Verlag, 1996. — Vol. 234. — ISBN 0-387-94656-X.
  4. ↑ Menezes, Alfred. Handbook of Applied Cryptography / Alfred Menezes, van Oorschot, Vanstone. — CRC Press, October 1996. — ISBN 0-8493-8523-7.

wikiredia.ru

A 325. Простые делители числа

ЗадачаДано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.

Входные данныеНатуральное число [latex]n[/latex]

Выходные данныеВсе его простые делители напечатанные через пробел

Тесты

входные данные выходные данные
2 2
7 7
50 2 5 5
169 13 13
583 11 53
2368 2 2 2 2 2 2 37
73890 2 3 3 5 821
885066 2 3 7 13 1621
6943960340 2 2 5 97 1787 2003

Код программы

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

    unsigned long long n;

  cin>>n;

    

    for (unsigned long long i = 2; i < sqrt(n)+0.00001; )    {

        if ( n % i == 0 ){

            std::cout << i << ' ';

            n /= i;

        }

        else{

            ++i;

        }

    }

    if ( n > 1 )

        std::cout << n;

    return 0;

}

Решение задачиДля решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.

Ссылки

Понравилось это:

Нравится Загрузка...

Похожее

This entry was posted in 3. Циклы and tagged алгебра, простые числа, циклы. Bookmark the permalink.

cpp.mazurok.com

ДЕЛИТЕЛИ и КРАТНЫЕ НАТУРАЛЬНОГО ЧИСЛА. ПРОСТЫЕ ЧИСЛА - ДЕЛИМОСТЬ НАТУРАЛЬНЫХ ЧИСЕЛ - Математика 6 класс - Н.А. Тарасенкова - Образование 2014

Раздел 1 ДЕЛИМОСТЬ НАТУРАЛЬНЫХ ЧИСЕЛ

 

В разделе узнаете:

- что такое делители и кратные натурального числа;

- какие есть признаки делимости чисел;

- какие числа называются простыми и как их находить;

- как разложить число на множители;

- что такое наибольший общий делитель чисел и как его находить;

- что такое наименьшее общее кратное чисел и как его находить;

- как применить изученный материал на практике

Решето ЭРАТОСФЕНА

 

 

§ 1. ДЕЛИТЕЛИ и КРАТНЫЕ НАТУРАЛЬНОГО ЧИСЛА. ПРОСТЫЕ ЧИСЛА

 

Посмотрите на рисунок 1. Вы видите, что бы яблок поделили на 2 кучки по Из яблока в каждой. Здесь число б является делимым, число 2 — делителем, а число С — долей. Но в яблок можно поделить и по-другому — разложить их на 3 кучки по 2 яблока в каждой. Тогда для делимого бы число 3 является делителем, а число 2 — долей. Это означает, что числа 2 и 3 являются делителями числа бы. В то же время число б является кратным для каждого из своих делителей для числа 2 и числа 3. Делители и кратные являются натуральными числами.

Рис. 1

 

Делителем числа называется такое число, на которое делится данное число.

Кратным числа называется такое число, которое делится предоставленное число.

? Или есть другие делители у числа? Так. Число бы делится еще на 1 и само на себя. Итак, в целом у числа 6 четыре делителя:

1; 2; 2; бы.

Обратите внимание:

каждое натуральное число, начиная с числа 2, имеет по крайней мере два делителя — число 1 и само это число. Другие делители ищут по специальным правилам.

Задача. Найдите все делители числа: 1) 7; 2) 12; 3) 25.

Решения.

1) У числа 7 есть по крайней мере два делителя — 1 и 7. На одно другое натуральное число 7 не делится, поэтому у него только два делителя: 1 и 7.

2) Число 12 имеет по крайней мере два делителя — 1 и 12. Далее последовательно проверяем делимость числа 12 на натуральные числа от 2 до 11.12 : 2 = б, поэтому 2 и 6 — делители числа 12. 12:3 = 4, поэтому 3 и 4 — тоже делители числа 12. На 5, 7, 8, 9, 10 и 11 число 12 не делится. Итак, делителями числа 12 е числа: 1; 2; 3;4; 6; 12.

3) В число 25 есть по крайней мере два делителя: 1 25. На 2, 3 и 4, а также на числа от 6 до 24 это число не делится. 25 : 5 = 5, число 5 является делителем числа 25, при чем дважды. Но уровне делители учитывают только один раз. Следовательно, у числа 25 не четыре, а три делителя: 1; 5; 25.

Запомните!

Натуральное число, которое имеет только два делителя (1 и само число), называется простым.

Натуральное число, имеющее больше двух делителей, называется составным.

Например, " 7 — простое число, а 12 и 25 — составлены.

? Является ли 1 простым числом? А составным? Нет, поскольку у числа 1 только один делитель. Итак, число 1 особенное. Вено и не простое и не составное.

Обратите внимание:

наименьшим простым числом является число 2.

Узнайте больше

Чтобы выписать некоторое количество простых чисел, можно воспользоваться способом, который придумал еще в III ст. к н. е. Эратосфен Киренский (276 г. к н. е. — 194 г. к н. е.), греческий математик, астроном, географ и поэт. В честь ученого этот способ носит название «решето Эратосфена». На рисунке (с. 4) вы видите, как находили простые числа от 2 до 50. Попробуйте самостоятельно объяснить, как это делали.

ВСПОМНИТЕ ГЛАВНОЕ

1. Какое число называется делителем числа?

2. Какое число называется кратным числа?

3. На какие два числа всегда делится любое натуральное число больше 1?

4. Какое натуральное число называется простым? Приведите пример.

5. Назовите наименьшее простое число.

6. Какое натуральное число называется составным? Приведите пример.

РЕШИТЕ ЗАДАЧИ

1'. Или каждое натуральное число имеет делители?

2'. Правильно ли, что число 3 является делителем числа:

1)5; 2)9; 3)4; 4)12?

3'. Правильно ли, что число 12 является кратным числа:

1)5; 2)9; 3)4; 4)3?

4'. Назовите: 1) три простых числа; 2) три составные числа.

5'. Является ли число 1:

1) простым числом; 2) составным числом?

6°. Дано числа: 3; 4; 6; 8; 9. Выпишите те из них, которые являются делителями числа: 1)8; 2) 12; 3) 16; 4) 18.

7°. Дано числа: 2; 3; 5; 6; 8. Выпишите те из них, которые являются делителями числа: 1)9; 2) 15; 3) 32; 4) 40.

8°. Найдите все делители числа: 1) 8; 2) 14; 3) 28; 4) 39.

9°. Найдите все делители числа: 1) 9; 2) 11; 3) 25; 4) 36.

10°. Дано числа: 10; 12; 14; 16; 18; 20. Выпишите те из них, которые являются кратными числа: 1) 4; 2) 6; 3) 3; 4) 8.

11°. Дано числа: 14; 18; 21; 24; 28; 30. Выпишите те из них, которые являются кратными числа: 1) 6; 2) 7; 3) 10; 4) 3.

12°. Дед Мороз принес детям в детский сад подарки и подарил каждому ребенку одинаковое их количество. Сколько подарков получил каждый ребенок, если в садике 64 ребенка, а подарков было:

1)256; 2) 320; 3)448?

13°. На координатном луче отметьте точку А(2) и еще четыре точки с координатами, кратными координате точки А.

14°. На координатном луче отметьте точку В(3) и еще три точки с координатами, кратными координате точки.

15°. Дано числа: 10; 11; 13; 15; 18; 23. Выпишите те из них, которые являются:

1) простыми; 2) составными.

16°. Дано числа: 21; 25; 27; 29; 32; 37. Выпишите те из них, которые являются:

1) простыми; 2) составными.

17°. Дано числа: 7; 8; 10; 13; 19; 24; 31; 34; 37; 39; 42; 43. Выберите среди них те, которые имеют:

1) только два делителя; 2) более двух делителей.

18. Сколько делителей имеет число:

1) 125; 2) 216; 3) 256; 4) 400?

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

1) 96; 2) 100; 3) 144; 4) 180.

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

1) 84; 2) 72; 3) 125; 4) 120.

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

1) 48 карандашей; 2) 64 карандаши; 3) 96 карандашей; 4) 120 карандашей?

Если да, то сколько коробок?

22. В спортивных соревнованиях принимают участие 108 школьников. Можно поделить их на команды:

1) по 6 человек; 2) по 12 человек; 3) по 16 человек; 4) по 24 человека?

Если да, то сколько будет таких команд?

23. Найдите все двоцифрові числа, которые являются кратными числа:

1)8; 2)13; 3)16; 4)22.

24. Найдите все двоцифрові числа, которые являются кратными числа:

1)9; 2)11; 3)12; 4)15.

25. Найдите все трицифрові числа, меньшие от 400, для которых число 35 является делителем.

26. Найдите четыре наименьшие числа, делителями которых являются числа 6 и 8.

27. Можно записать простое число в виде:

1) сумма двух четных чисел;

2) сумма двух нечетных чисел;

3) суммы четного и нечетного числа?

Ответ объясните. Приведите примеры.

28*. Найдите любые четыре натуральные числа, которые имеют ровно три делителя. Какую закономерность вы заметили?

29*. Найдите любые четыре натуральные числа, которые имеют ровно четыре делителя. Какую закономерность вы заметили?

30*. Запишите число 48 в виде разности квадратов двух простых чисел, меньших 25.

31. Оксанка покупала в магазине конфеты и получила 2 грн 25 коп. сдачи. Могла ли она получить сдачу только монетами: 1) по 5 к.; 2) по 10 к.; 3) по 25 к.; 4) по 50 к.? Если да, то сколько было монет?

32. Возраст Иринки, ее старшей сестры Ольги, их мамы и бабушки — все это являются делителями числа 165. Найдите возраст сестры, мамы и бабушки девочки, если известно, что Ирочке — 11 лет.

ЗАДАЧИ НА ПОВТОРЕНИЕ

33. Вычислите:

34. Магазин за первый день продал 180 кг помидоров, а за второй — 270 кг. На сколько процентов больше магазин продал помидоров за второй день?

schooled.ru

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

Образование 13 января 2018

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

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

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

В 17 веке прорыв в их изучении сделали Пьер Ферма и Марен Мерсенн. Первый сформулировал теорему, впоследствии названную его именем, согласно которой все числа вида 22n — простые, доказав ее для n =1..4. Однако впоследствии Леонардом Эйлером было показано, что при n=5 получается составное число. Параллельно с этим Марен Мерсенн выделил простые числа вида 2p - 1, в которых p – простое. Они интересны тем, что для них легко проверить соответствие критерию простоты. Учитывая этот факт, числа Мерсенна используют для выявления сверхбольших простых чисел. На данный момент предельное из известных выглядит как 277232917 − 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 = p1d1*p2d2 * …* pkdm (в другой формулировке: каноническое разложение числа n на простые сомножители имеет вид n = p1d1*p2d2*⋅ …⋅*pkdm), где p1<p2< … <pm — простые числа, и d1, … , dm— некоторые натуральные числа.

Кроме того, уже известную вам основную теорему арифметики можно перефразировать следующим образом: любое каноническое разложение 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=33;
  • таким образом, разложение 54 имеет вид 54 = 21 * 33, т.е. простые делители числа 54 — это "два" и "три".

Однако это не все, что мы хотели знать. Теперь найдем число простых делителей числа 54. Оно равно произведению степеней простых множителей канонического разложения числа n = p1*d1 p2d2*⋅ …⋅*pmdm, увеличенных на 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=2st.

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

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

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

Источник: fb.ru

monateka.com

A324. Делители одного числа, взаимно простые с другим

Задача

Даны целые числа [latex]p[/latex] и [latex]q[/latex]. Получить все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex].

Тесты

[latex]q[/latex] [latex]p[/latex] Все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex]
40 15 1 2 4 8
87 3 1 29

Код программы

Код программы на С++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

#include <iostream>

using namespace std;

unsigned long gcd(unsigned long x, unsigned long y) {

    return (y!=0) ? gcd(y,x%y) : x;

}

 

int main() {

    unsigned int q = 0, p;

    cin >> q >> p;

    for (unsigned int i = 1; i <= q; i++) {

        if((q % i) == 0) {

            if (gcd(i,p) == 1)

                cout << i << " ";

        }

    }

    return 0;

}

Код программы на Java

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

import java.util.*;

import java.lang.*;

import java.io.*;

 

class Ideone

{

    public static void main (String[] args) throws java.lang.Exception

    {

        int q = 0, p;

        Scanner in = new Scanner(System.in);

            

        q = in.nextInt();

        p = in.nextInt();

        

        for (int i = 1; i <= q; i++) {

            if((q % i) == 0) {

                if (gcd(i,p) == 1)

                    System.out.print(i + " ");

            }

        }

    }

    public static long gcd(long x, long y) {

            return (y!=0) ? gcd(y,x%y) : x;

    }

}

Решение

Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть [latex]m[/latex] и [latex]n[/latex] — не равные нулю целые неотрицательные числа, и пусть [latex]m\geq n[/latex]. Тогда, если [latex]n=0[/latex], [latex]GCD(n,m)=m[/latex], а если [latex]n\neq 0[/latex], то для числе [latex]m[/latex], [latex]n[/latex] и [latex]k[/latex], где [latex]k[/latex] — остаток от деления [latex]m[/latex] и [latex]n[/latex], выполняется равенство [latex]GCD(m,n)=GCD(n,k)[/latex].Для нахождения делителей числа [latex]q[/latex] взаимно простых с [latex]p[/latex], программа проверяет остатки от деления [latex]q[/latex] на все числа [latex]i[/latex] от [latex]1[/latex] до [latex]q[/latex]. Если остаток равен нулю, то число [latex]i[/latex] является делителем [latex]q[/latex]. Для каждого такого числа выполняется поиск наибольшего общего делителя (НОД — Greatest common divisor, GCD) [latex]i[/latex] и [latex]p[/latex] по алгоритму Евклида. Если найденный наибольший делитель равен 1, то числа [latex]i[/latex] и [latex]p[/latex] взаимно простые.

Ссылки

Условие задачиРешение задачи на сайте Ideone.com (C++)Решение задачи на сайте Ideone.com (Java)

Понравилось это:

Нравится Загрузка...

Похожее

This entry was posted in 3. Циклы and tagged взаимно простые числа, делители числа, С.А. Абрамов, циклы. Bookmark the permalink.

cpp.mazurok.com

Ł Общие делители и кратные Делители числа Взаимно простые числа

ШВЕЦОВ К.И., БЕВЗ Г.П.СПРАВОЧНИК ПО ЭЛЕМЕНТАРНОЙ МАТЕМАТИКЕАРИФМЕТИКА, АЛГЕБРА, 1965

СОДЕРЖАНИЕ ДАННОЙ СТАТЬИ

Поэтому

5600 = 2 · 2 · 2 · 2 · 2 · 5 · 5 · 7.

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

5500 = 25 · 52 · 7.

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

5. Разложение на множители больших чисел. Если данное число небольшое, или если оно делится на небольшое простое число, то его без особого труда можно разложить на множители. Но в общем случае разложение чисел на множители очень трудоемко. Например, не так легко разложить на множители сравнительно небольшое число 12091. Испытывая числа 2, 3, 5, 7, 11, 13, 17, 19, 23 и т.д., мы долгое время не можем обнаружить его делители. А ведь данное число не простое!

Несколько лет математики не могли разложить на множители число 549755813881. И только недавно электронная вычислительная машина обнаружила, что это число (оно равно 239 - 7) простое.

12. Общие делители и кратные

1. Делители числа. Делителем данного числа называется число, на которое данное число делится без остатка. Всякое простое число, например 13, имеет только два делителя: единицу и самого себя. Всякое составное число имеет более двух делителей, например число 6 имеет 4 делителя: 1, 2, 3 и 6. Чтобы найти делители данного составного числа, предварительно раскладывают его на простые множители; каждый из этих множителей будет простым делителем данного числа. Перемножением же простых множителей по два, по три, по четыре и т.д. получают составные делители данного числа.

Пример. Найти все делители числа 50.

Решение. 50 = 2 · 52, следовательно, 50 делится на 1, 2, 5, 2 · 5, 52, 2 · 52. Других делителей число 50 не имеет.

Ответ. 1, 2, 5, 10, 25, 50

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

Пример. Сколько делителей имеет число 5600?

Решение. 5600 = 25 · 52 · 7; (5 + 1) · (2 + 1) · (1 + 1) = 36.

Ответ. Число 5600 имеет 36 делителей.

2. Общий делитель нескольких чисел. Общим делителем нескольких чисел называется число, на которое все данные числа делятся без остатка. Например, числа 25 и 35 имеют общие делители: 1 и 5; числа 42 и 105 имеют общие делители: 1, 3, 7 и 21. Среди всех общих делителей всегда имеется наибольший. Это число называется наибольшим общим делителем (НОД). В наших примерах в первом случае НОД равен 5, во втором - 21.

Пишут: НОД (25, 35) = 5; НОД (42, 105) = 21.

Для нахождения наибольшего общего делителя нескольких чисел пользуются чаще всего двумя способами.

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

Пример. Найти НОД чисел: 210, 1260 и 245.

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

210 = 2 · 3 · 5 · 7; 1260 = 22 · 32 · 5 · 7; 245 = 5 · 72. Тогда НОД будет 5 · 7 = 35.

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

Пример. Найти НОД чисел 391 и 299.

Разделив число 391 на 299, получим в остатке 92. Разделив 299 на 92, получим в остатке 23. Разделив 92 на 23, получим в остатке 0. Следовательно, 23 есть НОД чисел 391 и 299.

Запись удобно расположить так:

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

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

Примеры. Числа 15 и 22 взаимно просты; числа 7, 19, 32 и 84 взаимно просты; числа 18 и 15 не взаимно просты, так как НОД (18, 15) = 3.

Если данных чисел больше двух и каждые два из них взаимно просты, то такие числа называют попарно взаимно простыми.

Примеры. 6, 9 и 4 - числа взаимно просты, но не попарно взаимно просты; числа 8, 9, 7 и 55 - попарно взаимно просты.

⇦ Ctrl предыдущая страница / страница 24 из 168 / следующая страница Ctrl ⇨мобильная версия страницы Смотрите также на этом сайте:ГАДАНИЯ, СОННИКИ, ЗАГОВОРЫ, НУМЕРОЛОГИЯ, ХИРОМАНТИЯ, ВУДУ, МАЯТНИК, ДЕНЕЖНАЯ МАГИЯВЯЗАНИЕ НА СПИЦАХ, КРЮЧКОМ, ТУНИССКОЕ ВЯЗАНИЕ, МОДЕЛИ ВЯЗАНОЙ ОДЕЖДЫ; ШИТЬЕ; МАШИННОЕ ВЯЗАНИЕРАЗНООБРАЗНЫЕ КУЛИНАРНЫЕ РЕЦЕПТЫ; ГОРШОЧКИ, МИКРОВОЛНОВКА; КОНСЕРВИРОВАНИЕСПРАВОЧНИКИ ПО ФИЗИКЕ, МАТЕМАТИКЕ, АНГЛИЙСКОМУ ЯЗЫКУ; ПОХУДЕНИЕ, АКУПУНКТУРА; НЕИСПРАВНОСТИ АВТОМОБИЛЯМНОЖЕСТВО ИСТОРИЧЕСКИХ ФАКТОВ О СОБЫТИЯХ, ОРУЖИИ И ОБМУНДИРОВАНИИ ВТОРОЙ МИРОВОЙ ВОЙНЫ; АРМЕЙСКИЕ БОТИНКИ ВСЕХ ВРЕМЕНПОПУЛЯРНЫЕ ПЕСЕННИКИ 1963-1987 гг.; ТОСТЫ, РОЗЫГРЫШИ, КОНКУРСЫ

Пользуйтесь поиском вверху страницы! Все, что будет найдено со значком Ł - относится к данному сайту



cartalana.org