Проблема поиска простых чисел очень остро стоит перед всеми, кто занимается математикой. Вопрос: какие числа называются простыми?
Простое число — это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными.
Один из самых известных алгоритмов для нахождения простых чисел в интервале до n - решето Эратосфена. Общая идея в следующем: найдя просто число, мы исключаем ни только само число, но и все числа, которые можно на найденное число поделить в данном интервале.
Рассмотрим решето по шагам:
1) Выпишем подряд все числа от 2 до n.
2) Пусть существует некоторая переменная, которая последовательно перебираем все простые числа. Пусть она называется p. (prime numbers)
3) Для первого простого числа возьмем значение равное 2.
4) Пройдем по всем числам после p, с шагом p, вычеркивая каждое из них.
5) Найдем первое не зачеркнутое число больше p и примем его за p.
6) Повторять до тех, пока p^2 не станет больше n.
Пример:
Пусть n=50.
Сложность решета Эратосфена
Оценим сложность приведенного алгоритма:
На каждой итерации мы делаем n/p вычеркиваний, где p - простое число. Есть следующая математическая формула:
Таким образом, сложность составляет:
n(ln(ln(n)))