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

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

Інструкція

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

Однак перебір може виявитися досить довгим, якщо, скажімо, на простоту потрібно перевірити число виду 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, а значить і делителями заданого числа вони не є.