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

Операцію уявлення натурального числа у вигляді добутку простих називають факторизації або розкладанням на прості множники. Поліноміальні алгоритми розкладання чисел невідомі, але також немає доказів того, що в природі вони не існують.

На складності обчислень, пов`язаних з факторизації чисел, засновані деякі криптосистеми, наприклад, однією з відомих є RSA. Для квантових комп`ютерів існує алгоритм Шора, який дозволяє здійснювати факторизацию чисел з поліноміальною складністю.

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

Ще Евклидом був доведений той факт, що простих чисел існує нескінченно багато. Суть його докази, представленого в книзі «Начала», полягає в наступному. Нехай існує кінцеве число простих чисел. Перемножимо їх, після чого додамо до них одиницю. Число, яке вийшло, не може бути розділене на жодне просте число з кінцевого набору без залишку (він буде дорівнює 1). В такому випадку це число ділиться на просте число, яке не входить до складу представленого кінцевого набору. Крім цього, існують також і інші математичні докази нескінченності простих чисел.

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

Однак перебір може виявитися досить тривалим, якщо, скажімо, на простоту потрібно перевірити число виду 136827658235479371. Тому варто звернути увагу на правила, здатні помітно скоротити час обчислень.

Якщо число складене, тобто представляє собою твір простих співмножників, то серед цих співмножників обов`язково повинен знайтися хоча б один, який буде менше квадратного кореня з заданого числа. Адже твір двох чисел, кожне з яких більше квадратного кореня з деякого X, буде свідомо більше X, і ці два числа ніяк не можуть бути його дільниками.

Тому навіть при простому переборі можна обмежитися перевіркою тільки тих цілих чисел, які не перевищують квадратний корінь з заданого числа, округлений в більшу сторону. Наприклад, перевіряючи число 157, ви перебирає можливі множники тільки від 2 до 13.

Якщо у вас немає під рукою комп`ютера, і число на простоту доводиться перевіряти вручну, то і тут на допомогу приходять прості і очевидні правила. Найбільше вам допоможе знання вже відомих простих чисел. Адже перевіряти окремо подільність на складові числа немає сенсу, якщо можна перевірити подільність на їх прості множники.

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

Числа, що діляться на 5, завжди закінчуються п`ятіркою або нулем. Погляд на останню цифру числа допоможе їх відсіяти.

Якщо число ділиться на 3, то і сума його цифр теж обов`язково ділиться на 3. Наприклад, сума цифр числа 136827658235479371 дорівнює 1 + 3 + 6 + 8 + 2 + 7 + 6 + 5 + 8 + 2 + 3 + 5 + 4 + 7 + 9 + 3 + 7 + 1 = 87. Це число ділиться на 3 без залишку: 87 = 29 * 3. Отже, і наше число теж ділиться на 3 і є складовим.

Дуже простий також ознака подільності на 11. Потрібно з суми всіх непарних цифр числа відняти суму всіх парних його цифр. Парність і непарність визначається рахунком з кінця, тобто з одиниць. Якщо вийшла різниця ділиться на 11, то і все задане число теж на нього ділиться. Наприклад, нехай дано число 2576562845756365782383. Сума його парних цифр дорівнює 8 + 2 + 7 + 6 + 6 + 7 + 4 + 2 + 5 + 7 + 2 = 56. Сума непарних: 3 + 3 + 8 + 5 + 3 + 5 + 5 + 8 + 6 + 6 + 5 = 57. Різниця між ними дорівнює 1. Це число не ділиться на 11, а отже, 11 не є дільником заданого числа.

Перевірити подільність числа на 7 і 13 можна аналогічним способом. Розбийте число на трійки цифр, починаючи з кінця (так роблять при друкарською запису для зручності читання). Число +2576562845756365782383 перетворюється в 2 576 562 845 756 365 782 383. Підсумуйте числа, які стоять на непарних місцях, і відніміть з них суму чисел на парних. В даному випадку ви отримаєте (383 + 365 + 845 + 576) - (782 + 756 + 562 + 2) = 67. Це число не ділиться ні на 7, ні на 13, а значить і делителями заданого числа вони не є.