Какие существуют способы определения простых чисел без использования компьютера?

Несколько способов определить простое число без использования компьютера:

• Пробное деление. 23 Нужно поделить проверяемое число на все простые числа от 2 до квадратного корня из этого числа. 3 Если число ни на какое другое, кроме единицы и самого числа, больше не делится, значит, оно простое. 3
• Решето Эратосфена. 35 Это алгоритм, разработанный греческим математиком Эратосфеном. 3 Нужно записать все числа от 2 до N (где N — это верхняя граница, до которой ищут простые числа). 3 Затем: 3

1. Начать с первого числа (2) — это первое простое число. 3
2. Вычеркнуть все числа, кратные 2 (то есть 4, 6, 8, 10…), так как они не являются простыми. 3
3. Перейти к следующему незачеркнутому числу (это будет 3) — это следующее простое число. 3
4. Вычеркнуть все числа, кратные 3 (6, 9, 12, 15…), если они ещё не вычеркнуты. 3
5. Повторить процесс: переходить к следующему незачеркнутому числу, объявлять его простым и вычёркивать все его кратные. 3
6. Остановиться, когда дойдёт до числа, которое больше √N (квадратного корня из N). 3 Все оставшиеся незачеркнутые числа будут простыми. 3

• Визуальные признаки. 2 Простые числа обычно оканчиваются на 1, 3, 7 и 9. 2 Из этого правила есть исключения: например, 21, 27, 33, 39, 49 и другие — составные числа. 2