Кожен школяр знає, що всі числа діляться на прості і складові. Більше того, тим, хто ретельно вивчає математику, відомі і їх властивості. Однак якщо відповідь на питання, скільки дільників має просте число, прихований у самому визначення цього поняття, то з'ясувати кількість простих дільників для заданого — досить складна задача. Вона вирішується із застосуванням методу перебору і імовірнісних алгоритмів, реалізованих на ЕОМ.

Трохи історії

Достовірно відомо, що серйозним вивченням властивостей простих чисел першими стали займатися стародавні греки. Однак про їх існування було відомо за кілька тисячоліть до того, як Арістотель включив теореми про їх властивості в свої знамениті "Початку". Стародавні греки придумали і решето Ератосфена, представляє собою алгоритм знаходження простих чисел з проміжку[1,n].


У 17 столітті прорив у вивченні зробили П'єр Ферма і Марен Мерсенн. Перший сформулював теорему, згодом названу його ім'ям, згідно з якою всі числа виду 2 2n — прості, довівши її для n =14. Однак згодом Леонардом Ейлером було показано, що при n=5 виходить складене число. Паралельно з цим Марен Мерсенн виділив прості числа виду 2 p - 1 в яких p – просте. Вони цікаві тим, що для них легко перевірити відповідність критерію простоти. Враховуючи цей факт, числа Мерсенна використовують для виявлення надвеликих простих чисел. На даний момент граничне з відомих виглядає як 2 77232917 – 1 . Крім того, їх широко використовують при створенні генераторів випадкових чисел, що мають широке застосування на практиці. Велику роль у дослідженні простих чисел зіграли також Лежандра і Гаусс. Ці вчені висунули гіпотезу про їх щільності.

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

Якщо можна відразу ж назвати прості дільники числа 4 то для великих чисел зробити це зазвичай досить важко. Про рішення цієї проблеми люди стали замислюватися ще кілька тисячоліть тому. Зокрема, давньогрецький математик Ератосфен, який жив на межі третього і другого століть до Різдва Христового придумав алгоритм знаходження всіх простих чисел, менших цілого числа n.


Він отримав назву решета, так як «просіює» або по-сучасному «фільтрує» всі числа, крім простих. Алгоритм складається з наступних команд:

виписати всі цілі числа від 2 до n;

присвоїти змінній значення p 2 так як це найменше просте число;

закреслити в списку всі числа від 2p до n, кратні p;

присвоїти значення змінної p значення першого, не закресленого числа записаної послідовності, яка більше p;

повторювати 3-й і 4-й, поки можливо.

Якщо все зроблено правильно, то у списку залишаться не закресленими всі прості числа від двох до n. Для реалізації решета Ератосфена на електронно-обчислювальній машині використовують модернізований алгоритм. На 3-му кроці можна закреслювати числа, починаючи з числа p 2 , так як всі складові числа, які менші нього, до цього часу вже будуть закреслені. Тоді зупинка роботи алгоритму повинна відбутися, коли виконається умова p 2 >n.
Слід також врахувати, що всі прості числа, за винятком двійки, — непарні, тому, починаючи з p2 можна «фільтрувати» за 2p.

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

Згідно з визначенням, просте число має два дільника. Один з них — 1 а другий — сама ця величина. Перш ніж з'ясувати, яка кількість простих дільників числа, варто приділити трохи часу вивченню основної теореми арифметики. Згідно їй, натуральне число n > 1 можна уявити, як n = p 1 * ·*p k , де p 1 , , p m — прості числа. При цьому таке подання є єдиним з точністю до порядку слідування його співмножників. Наслідок цієї теореми можна сформулювати наступним чином: будь-яке натуральне число n представимо у вигляді n = p 1 d1 *p 2 d2 * * p k d m (у іншому формулюванні: канонічне розкладання числа n на прості множники має вигляд n = p 1 d1 *p 2 d2 *· ·*p k d m ), де p 1 2 < … m — прості числа, і d 1 , , d m — деякі натуральні числа. Крім того, вже відому вам основна теорема арифметики можна перефразувати наступним чином: будь-канонічне розкладання n можна вважати тотожними, якщо не звертати уваги на порядок дільників. Це означає, що на практиці для значної частини чисел існує безліч досить простих алгоритмів їх розкладання на прості множники, які в результаті дають один і той же результат.

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

Перш ніж з'ясувати, як можна знайти найбільший простий дільник числа (НПД) n, слід розібратися з іншим важливим питанням. Отже, з'ясуємо, за яким алгоритмом можна встановити, чи є у величини інші дільники крім одиниці і його самого. Зробити це можна шляхом перебору простих чисел p 1 , p k . Причому завершити цикл можна, як тільки p i+1 , для якого проводилася перевірка, буде задовольняти умові (pi +1 ) 2 > n. Дамо пояснення, чому перебір можна обмежити p i >=sqr(n). Припустимо, у числа n, досліджуваного на простоту є деякий дільник p. Тоді d=n/p так само буде його дільником. Але, так як d і p — різні числа, жоден з них не може бути більше кореня n.

Як знайти найбільший простий дільник числа n

Знайти НПД n, можна, діючи за такою схемою:

Поділити n на два, якщо воно парне або на три, якщо непарне. Виняток становить n, остання цифра десяткового запису якого нуль або п'ять. Таке число можна відразу розділити на п'ять.

Якщо результат не ціле число, то ділять n на наступні цілі числа, перебираючи їх аж до p i >=sqr(n).

Над отриманим числом n 1 виробляють всі дії в тому ж порядку, що представлений вище, тільки з умовою p i >=sqr(n 1 ). Якщо ж ні на одному з кроків перебору n 1 не ділиться на одне з простих чисел, то n ціле і є своїм же НПД. В іншому випадку отримуємо n 2 і продовжуємо ділення з перебором до моменту, коли на (i+1) кроці встановимо, що n i — ціле.

Приклад

Знайдемо прості дільники числа 276.

ділимо на "два";

отримуємо 138;

так як число парне, то знову ділимо на "два";

результат — 69;

ділимо на наступне просте число "три";

отримуємо 23.

Так як це число просте, можемо підвести підсумок. Простими дільниками 276 є 2 3 і 23.

Як знайти кількість простих дільників числа

Якщо мова йде про цілому малому числі, то рішення такої задачі не представляє ніякої складності. Розглянемо конкретний приклад. Знайдемо прості дільники числа 54. Для цього:

54 ділимо на "два" і отримуємо 27;

27 непарна, тому розділимо його вже не на "два", а на наступне просте число, тобто "три";

зауважимо, що 27=3 3 ;

таким чином, розкладання 54 має вигляд 54 = 2 1 * 3 3 , тобто прості дільники числа 54 — це "два" і "три".

Однак це не все, що ми хотіли знати. Тепер знайдемо кількість простих дільників числа 54. Воно дорівнює добутку ступенів простих множників канонічного розкладання числа n = p 1 * d1 p 2 d2 *· ·*p m d m , збільшених на 1. Іншими словами, в загальному випадку K = (d 1 +1)** (d m +1). Тоді для 54 маємо До = 2 * 4 = 8 тобто загальне число дільників дорівнює восьми. Зверніть увагу, що все значно спростилося, якщо б мова йшла про 2337103 та ін, так як кожен знає, скільки дільників у простого числа.

Приклад

Знайти кількість простих дільників числа 9990.

так як число 9990 закінчується на цифру "нуль", то воно ділиться на п'ять і на два.

маємо 999.

в результаті розподілу на три маємо 333;

знову ділимо на три, отримуємо 111;

ділимо на три, маємо 37;

37 просте число, так як не ділиться без остачі на жодне з простих чисел, що знаходяться між двійкою і коренем з числа 37;

підраховуємо кількість простих дільників числа 9990. Це 235 і 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 ). Тепер ви знаєте, скільки дільників має просте число і як з'ясувати найбільш примітивний алгоритм обчислення НПД. Ці знання допоможуть вам у вирішенні багатьох практичних завдань.