Простые числа и решето Эратосфена: вычисления с делимостью

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

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