Прості числа та решето Ератосфена: обчислення з подільністю

Коротко: Прості числа діляться лише на 1 і на себе; решетом Ератосфена швидко знаходять усі до n, а складність їх розкладання на множники забезпечує безпеку шифрування на кшталт RSA.

Докладніше: Просте число — натуральне число > 1 рівно з двома дільниками (1 і воно саме): 2, 3, 5, 7, 11, 13 … Будь-яке число однозначно розкладається на прості множники (основна теорема арифметики): 360 = 2³ · 3² · 5.