Как определить простое число?

Простое число – это число, которое можно разделить только на 1 или на него самого. Есть не мало способов определить простое число. Разработано много специализированных тестов простоты, например, тест Люка-Лемера, созданный в 1878 году французским математиком Люка и доработанный

1. Лемером, американским математиком.
Очень распространенный способ — так называемое решето Эратосфена. Для того, чтобы определить простое число этим методом нужно выписать по порядку все целые числа, начиная с одного и заканчивая определенным значением Х.

2. Сначала вычеркиваем из списка все числа, которые можно разделить на 2, затем берем следующее после 2 число и зачеркиваем все числа, которые можно на него разделить.

3. Продолжать нужно до тех пор, пока выбранное число не окажется больше, чем Х/2. Те числа, которые остались не вычеркнутыми – простые.
Есть и другие методы.

1. Так как простое число не делится ни на какое другое, кроме себя самого и единицы, то самый простой способ его вычислить – попытаться разделить на все числа меньше его по значению. В теории, конечно, это выглядит просто, а вот на практике…

2. Но все же есть способы облегчить задачу
Во-первых, поможет определить простое число последняя цифра. Если это пять, ноль или четное число, то оно, соответственно, не может быть простым .

3. Исключение составляет число 2, так как оно делится на 1 и самого себя. Все остальные можно разделить на 5 или 2.

1. Еще один вариант упростить задачу – разбить число на отдельные цифры, сложить их и сумму разделить на 3. Если итог получился без остатка, то число не простое.

2. Далее выясняем может ли нужное вам число разделить на 11. Для этого опять разбиваем его на отдельные цифры. Сначала плюсуем четные, затем отдельно нечетные.

3. Далее от суммы первых отнимаем сумму вторых. Делим на 11. Если итог делится без остатка на 11, то число не может быть простым.

4. Теперь отметем еще два варианта чисел: те, которые можно разделить на 13 и 7. Для этого нужно разбить число на группы по три цифры, начиная с конца. Затем суммируем. Сначала те группы цифр, которые находятся на нечетных местах, потом те, что на четных. Далее от итога первых отнимаем итог вторых и результат делим на семь и тринадцать.