Всякое натуральное число делится на себя и на 1: это видно из равенства a = a · 1.
Натуральные числа, у которых ровно два различных делителя — само число и 1, называются простыми: например, 2, 3, 5, 7, 89. Числа, у которых больше двух делителей, называются составными: например, 6 — у него четыре делителя 1, 2, 3, 6. У числа 1 делитель один, и оно не простое и не составное.
Значит, натуральные числа делятся на три части: число 1; простые числа (ровно 2 делителя); составные числа (больше 2 делителей).
Сказать, что число составное, — значит высказать утверждение о существовании: у него есть хотя бы один делитель, не равный ни 1, ни самому числу. Иначе говоря, составное число можно разложить на два множителя, ни один из которых не равен 1: 21 = 3 · 7. А у простого числа в любом разложении на два множителя один множитель равен 1, а другой — самому числу.
Понятие простого числа появилось у Пифагора ещё в VI веке до н. э., а в III веке до н. э. Евклид доказал, что простых чисел бесконечно много. Его современник Эратосфен придумал, как составить список простых чисел: выписать числа подряд, вычеркнуть 1, а потом по очереди вычёркивать кратные первого ещё не вычеркнутого числа (кроме него самого) — кратные 2, 3, 5, 7 и т. д. Греки писали на восковых табличках и не вычёркивали числа, а прокалывали их иглой, поэтому табличка в конце становилась похожей на решето — отсюда название «решето Эратосфена». Вот что остаётся от чисел до 40 (простые выделены):
| cancel1 | 2 | 3 | cancel4 | 5 |
|---|---|---|---|---|
| cancel6 | 7 | cancel8 | cancel9 | cancel10 |
| 11 | cancel12 | 13 | cancel14 | cancel15 |
| cancel16 | 17 | cancel18 | 19 | cancel20 |
| cancel21 | cancel22 | 23 | cancel24 | cancel25 |
| cancel26 | cancel27 | cancel28 | 29 | cancel30 |
| 31 | cancel32 | cancel33 | cancel34 | cancel35 |
| cancel36 | 37 | cancel38 | cancel39 | cancel40 |