Что такое простое число

Простым числом называют натуральное число, у которого есть только два делителя – единица и само это число.
Единица не относится к простым числам.
 
Пример.
Указать, какие натуральные числа из записанных ниже будут простыми:
2; 7; 13; 18; 29; 34; 37; 71; 87; 103.
 
Ответ. 2; 7; 13; 29; 37; 71; 103.

Чтобы проверить, является ли число простым, нужно попробовать разложить его на простые множители. Такое разложение принято выполнять от самого наименьшего простого числа 2 и двигаться к увеличению простых чисел. То есть сначала проверяем, делится ли число на 2, затем на 3, далее на 7, на 11, на 13 и т.д.
Существует таблица простых чисел, которой можно пользоваться (если она есть под рукой) без попыток разложения числа на простые множители.

Также существует довольно распространенный метод, предложенный еще в III веке до н.э. Эратосфеном, который так и называется «решето Эратосфена». Метод позволяет найти все простые числа в любом числовом промежутке.
Алгоритм работы метода:

1. Выписывают все числа из нужного числового промежутка.
2. Из него вычеркивают каждое второе число, начиная с числа 2, так как они являются кратными числу 2.
3. Далее вычеркивают каждое третье число после числа 3, так как все они делятся на 3.
4. И так вычеркивают каждое число, кратное следующему невычеркнутому числу в записанном ряде чисел. Числа, которые остались невычеркнутыми, являются простыми.