Натуральні числа можна поділити на три класи: одиниця (має один натуральний дільник), просте число (має два натуральні дільники), складове число (Має більше двох натуральних дільників). Як простих, і складових чисел нескінченно багато.
Просте число – це натуральне число більше 1, у якого є всього два дільники: одиниця і саме число. Наприклад: 11, 13, 17, 19 – список простих чисел. 11 – ділиться тільки на 1 та 11.
Нагадаємо, що простими числами називаються такі числа, Які без залишку діляться тільки на себе або на 1. Наприклад: 2, 3, 5, 7, 11 – це все прості числа.
Братимемо по черзі натуральні числа , починаючи з двійки, та перевіряти їх на простоту. Перевірка на простоту полягає в наступному: перебираючи числа з діапазону від до , ділитимемо на з залишком. Якщо при якомусь виявиться нульовий залишок, значить, ділиться на ціле, і число складова.