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

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

Інструкція

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

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

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

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

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