Как происходит поиск простых чисел среди натуральных чисел?

Поиск простых чисел среди натуральных чисел можно осуществлять с помощью алгоритма, известного как «решето Эратосфена». 13

Алгоритм: 1

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

Ещё один способ поиска простых чисел — пробное деление. 1 Нужно поделить проверяемое число на все простые числа от 2 до квадратного корня из этого числа. 1 Если число ни на какое другое, кроме единицы и самого числа, больше не делится, значит, оно относится к множеству простых чисел. 1