Як визначити просте число.

Простими числами називаються ті цілі числа, які не діляться без залишку на жодне інше число, крім одиниці і самого. В силу різних причин вони із старовини цікавили математиків. Це призвело до розвитку різних способів перевірки, чи є задане число простим.
Інструкція
1
Оскільки просте число за визначенням не повинно ділитися ні на яке інше, крім себе самого, очевидний спосіб перевірки числа на простоту - спроба розділити його без залишку на все числа, менші його. Саме цей спосіб зазвичай вибирають творці комп'ютерних алгоритмів.
2
Однак перебір може виявитися досить довгим, якщо, скажімо, на простоту потрібно перевірити число виду 136827658235479371. Тому варто звернути увагу на правила, здатні помітно скоротити час обчислень.
3
Якщо число складене, тобто представляє собою твір простих співмножників, то серед цих співмножників обов'язково повинен знайтися хоча б один, який буде менше квадратного кореня із заданого числа. Адже твір двох чисел, кожне з яких більше квадратного кореня з деякого X, буде свідомо більше X, і ці два числа ніяк не можуть бути його дільниками.
4
Тому навіть при простому переборі можна обмежитися перевіркою тільки тих цілих чисел, які не перевищують квадратний корінь з заданого числа, округлений в більшу сторону. Наприклад, перевіряючи число 157, ви перебираєте можливі множники тільки від 2 до 13.
5
Якщо у вас немає під рукою комп'ютера, і число на простоту доводиться перевіряти вручну, то і тут на допомогу приходять прості і очевидні правила. Найбільше вам допоможе знання вже відомих простих чисел. Адже перевіряти окремо подільність на складові числа немає сенсу, якщо можна перевірити подільність на їх прості множники.
6
Парне число за визначенням не може бути простим, оскільки ділиться на 2. Тому, якщо остання цифра числа парна, то воно явно складене.
7
Числа, що діляться на 5, завжди закінчуються п'ятіркою або нулем. Погляд на останню цифру числа допоможе їх відсіяти.
8
Якщо число ділиться на 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 і є складовим.
9
Дуже простий також ознака подільності на 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 не є дільником заданого числа.
10
Перевірити подільність числа на 7 і 13 можна аналогічним способом. Розбийте число на трійки цифр, починаючи з кінця (так роблять при друкарською записи для зручності читання). Число +2576562845756365782383 перетворюється на 2 576 562 845 756 365 782 383. Підсумуйте числа, які стоять на непарних місцях, і відніміть з них суму чисел на парних. В даному випадку ви отримаєте (383 + 365 + 845 + 576) - (782 + 756 + 562 + 2) = 67. Це число не ділиться ні на 7, ні на 13, а значить і делителями заданого числа вони не є.
Зверніть увагу
Ознаки подільності на інші прості числа набагато складніше, і в більшості випадків простіше спробувати розділити заданий число на передбачуваний дільник вручну.