2.1 Простые числа. Решето Эратосфена

Каждое натуральное число, большее единицы, делится, по крайней мере, на два числа: на 1 и на само себя. Если ни на какое другое натуральное число оно нацело не делится, то называется простым, а если у него имеются ещё какие-то целые делители, то составным. Единичка же не считается ни простым числом, ни составным.

Небольшую "коллекцию" простых чисел можно составить старинным способом, придуманный ещё в 3 в. до н. э. Эратосфеном Киренским, хранителем знаменитой Александрийской библиотеки.

Выпишем несколько подряд идущих чисел, начиная с 2. Двойку отберём в свою коллекцию, а остальные числа, кратные 2, зачеркнем. Ближайшим незачёркнутым числом будет 3. Возьмём в коллекцию и его, а все остальные числа, кратные 3, зачеркнем. При этом окажется, что некоторые числа уже были вычеркнуты раньше, как, например, 6, 12 и др. Следующее наименьшее незачёркнутое число - это 5. Берем пятерку, а остальные числа, кратные 5,зачеркиваем. Повторяя эту процедуру снова и снова, в конце концов добьемся того, что незачеркнутыми останутся одни лишь простые числа - они словно просеялись сквозь решето. Поэтому такой способ и получил название "решето Эратосфена".

Простых чисел бесконечное множество.