Советы по определению простых чисел

Советы по работе с простыми числами

Быстрое определение простоты числа — полезный навык. Эти приёмы помогут.

Исключайте чётные числа

Все чётные числа, кроме 2, составные. Это сразу исключает половину всех чисел.

Проверяйте делимость на малые простые

Для чисел до 100 достаточно проверить делимость на 2, 3, 5 и 7. Если число не делится ни на одно из них — оно простое.

Используйте правило корня

Проверяйте делители только до квадратного корня из числа. Для числа 97 достаточно проверить делители до 9 (поскольку 10² = 100 > 97).

Запомните простые числа до 100

Их всего 25: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Запомните хотя бы первые 15.

Правило 6k ± 1

Все простые числа, кроме 2 и 3, имеют вид 6k - 1 или 6k + 1. Это значит, что простые числа находятся по соседству с числами, кратными 6.

Числа Мерсенна

Числа вида 2ⁿ - 1 часто бывают простыми (при простом n). Это используется для поиска рекордно больших простых чисел.

Не путайте с взаимно простыми

Два числа могут быть взаимно простыми (НОД = 1), даже если каждое из них составное. Например, 8 и 15 взаимно просты.

Смотрите также: НОД и НОК, Факториал и Комбинаторика, Калькулятор дробей