Що таке просте число.

Простим числом називається натуральне число, яке ділиться тільки на одиницю і саме на себе. Всі інші числа, крім одиниці, є складовими. Властивості простих чисел вивчає наука під назвою теорія чисел.
Інструкція
1
Згідно з основною теоремою арифметики, будь-яке натуральне число, яке більше одиниці, може бути розкладено на твір простих чисел. Виходячи з цього, можна зробити висновок про те, що прості числа являють собою певні «блоки» для натуральних чисел.
2
Операцію уявлення натурального числа у вигляді добутку простих називають факторизації або розкладанням на прості множники. Поліноміальні алгоритми розкладання чисел невідомі, але також немає доказів того, що в природі вони не існують.
3
На складності обчислень, пов'язаних з факторизації чисел, засновані деякі криптосистеми, наприклад, однією з відомих є RSA. Для квантових комп'ютерів існує алгоритм Шора, який дозволяє здійснювати факторизацию чисел з поліноміальною складністю.
4
Існують алгоритми, за допомогою яких можна здійснювати пошук, а також розпізнавати прості числа. Найпростішими з них є решето Ератосфена, решето Аткіна, Решето Сундарама. На ділі ж часто постає завдання не отримання простих чисел, а перевірки числа на те, чи є воно простим. Алгоритми, покликані вирішувати подібні завдання, іменуються тестами простоти.
5
Ще Евклидом був доведений той факт, що простих чисел існує нескінченно багато. Суть його докази, представленого в книзі «Начала», полягає в наступному. Нехай існує кінцеве число простих чисел. Перемножимо їх, після чого додамо до них одиницю. Число, яке вийшло, не може бути розділене ні на яке просте число з кінцевого набору без залишку (він буде дорівнює 1). У такому випадку це число ділиться на просте число, яке не входить до складу представленого кінцевого набору. Крім цього, існують також й інші математичні докази нескінченності простих чисел.
Відео по темі
 http://www.youtube.com/watch?v=pDuyU70UIKA
Простими числами називаються ті цілі числа, які не діляться без залишку на жодне інше число, крім одиниці і себе самого. В силу різних причин вони з давнини цікавили математиків. Це призвело до розвитку різних способів перевірки, чи є задане число простим.
Інструкція
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, а значить і делителями заданого числа вони не є.
Зверніть увагу
Ознаки подільності на інші прості числа набагато складніше, і в більшості випадків простіше спробувати розділити заданий число на передбачуваний дільник вручну.