Будемо брати по черзі натуральні числа , починаючи з двійки, і перевіряти їх на простоту. Перевірка на простоту полягає в такому: перебираючи числа з діапазону від до , будемо ділити на із залишком. Якщо при якомусь виявиться нульовий залишок, значить, ділиться на націло, і число складене .

Натуральне число , більше за 1 , називається простим , якщо воно ні на що не ділиться, крім себе та 1 . Іншими словами, n > 1 – просте, якщо під час його ділення на будь-яке число, крім 1 і n, є залишок. Наприклад, 5 це просте число , воно не може бути поділене без залишку на 2 , 3 і 4 .

Якщо ділиться, то змінна k , що виконує роль лічильника, збільшується на одиницю. Якщо число дільників дорівнює 0 , то число, що перевіряється, є простим .

n = p1 – p2 – … – p. числа n на (кінцеве число ) простих множників p1, p2, … , pt називається розкладанням на прості множники числа n. Основну теорему арифметики можна перефразувати таким чином: будь-яке розкладання на прості числа буде тотожним з точністю до порядку дільників.