Простое число — это число, которое делится нацело без остатка только на 1 и на самого себя. Также известно, что любое целое число, большее 1, является либо простым, либо может быть выражено как произведение простых чисел. Ряд простых чисел начинается с 2 и имеет следующий вид: 2, 3, 5, 7 и т.д.
Рассмотрим более-менее оптимальный алгоритм поиска простых чисел. Для этого давайте реализуем на Java метод getFirstPrimes(), который будет возвращать N первых простых чисел.
Все найденные простые числа будем складывать в список. Далее проверяем, что если у нас запросили хотя бы одно простое число, то сразу добавим 2, т.к. с него начинается последовательность. Далее в цикле начинаем проверять числа, сразу начиная с трёх. Также обратите внимание, что мы проверяем только нечётные числа (приращение +2), т.к. все чётные числа по определению делятся на 2.
Цикл выполняется до тех пор, пока в нашем результирующем списке не окажется ровно столько простых чисел, сколько у нас запросили. Саму проверку на «простоту» выполняем с помощью метода isPrime(), которому передаём текущее проверяемое число и уже накопленные нами на предыдущих итерациях числа.
Здесь мы сначала вызываем метод Math.sqrt(), ведь если проверяемое число состоит хотя бы из двух множителей, то ни одно из них не может превышать двоичный корень.
Затем в цикле проходим по всем уже найденным простым числам и по очереди пытаемся делить на них текущее число. Если число делится на простое число без остатка — значит, оно составное. Проверку выполняем до тех пор, пока простые числа меньше корня из проверяемого числа.
Рассмотренный алгоритм работает довольно быстро. За пару секунд он находит 500 000 простых чисел.
Оптимизации, которые мы применили:
- проверяем только нечётные числа
- пытаемся делить только на уже найденные простые числа
- делителями могут быть только те простые числа, которые не превосходят квадратного корня из проверяемого числа
Последняя оптимизация оказалась наиболее существенной.
Натуральное число, большее 1 , называется простым, если оно ни на что не делится, кроме себя и 1 .
Другими словами, n > 1 – простое, если при его делении на любое число кроме 1 и n есть остаток.
Например, 5 это простое число, оно не может быть разделено без остатка на 2 , 3 и 4 .
Напишите код, который выводит все простые числа из интервала от 2 до n .
Для n = 10 результат должен быть 2,3,5,7 .
P.S. Код также должен легко модифицироваться для любых других интервалов.
Существует множество алгоритмов решения этой задачи.
Всем хорошего дня!
Конечно перечислять все я не буду, достаточно просто заглянуть сюда.Уже довольно большой период времени я наблюдаю за развитием темы простых чисел. И мне все больше хочется называть эти числа не простыми, а гениальными. И это не просто мое желание. Достаточно вспомнить высказывания великих людей: «Простота — это то, что труднее всего на свете; это крайний предел опытности и последнее усилие гения.» Леонардо да Винчи; «Всё гениальное просто, и всё простое гениально.» Йозеф Геббельс.Хочется отметить, что простые числа занимают далеко не последнее место в криптографии.Существует множество алгоритмов нахождения простых чисел. Но описать их последовательность аналитически, найти закономерность, еще никому не удавалось. Давайте же посмотрим на числа и поищем среди них простые. Для определения любого простого числа нужно попробовать разделить это число на числа лежащие в диапазоне от 1 до проверяемого на простоту числа. С числами до 100 проблем не возникает и можно интуитивно сказать является ли число простым, попробуйте! Но как быть дальше? Первое что приходит в голову это калькулятор, а лучше компьютер. Однозначно нужна программа!Существующие методы на первый взгляд кажутся громоздкими и не прозрачными, сложными. И это понятно, ведь это лучшее что имеется на сегодня, они оптимизированы по возможности на максимум, прогнаны через сотни не худших голов планеты. Разбираться в готовом коде не хотелось. Для большей глубины понимания проблемы, хотелось пройти путь самостоятельно, как первопроходец. И я решил изобрести свой велосипед и написал немного на Java. Я знал, что некоторая реализация уже имеется в исходниках JDK, но не стал с ней знакомится.
Пишем алгоритм поиска простых чисел
Так я начал. Хочу сказать сразу, что я не гнался за супер производительность кода и о параллельности потоков не думал, мне хотелось чего-то простого пусть и не самого быстрого. После двух часов прокручивания различных схем, мне показалось, что это далеко не легкая задача. В один момент я даже подумал, что мне не хватает определенных навыков и знаний. Все мои попытки сводились к перебору чисел и проверки на делимость каждого числа на числа лежащие в соответственном диапазоне. При этом я пытался считать на сколько чисел мое данное число разделилось на цело, а на сколько дробно, потом сравнивал их с существующим количеством элементов в диапазоне. «Это число не делится ни на одно другое кроме себя и единицы»-крутилось у меня в голове. Все время я пытался сосчитать элементы на которые не делится текущее число. Что не приводило к нужному результату. Мне пришлось отложить задачу. Позже, одним вечером, беседуя со своей женой я осознал свою грубейшую ошибку. Все дело было в неправильном подходе к решению. «Просто сделай проверку на количество делителей, у простого числа их всегда будет только два и не больше» — подсказала мне любимая. Действительно у любого другого из числа из натуральных их будет больше. В тот же вечер был написан код.
Пока я не могу сказать на сколько алгоритм работает медленнее существующих. Конечно с увеличением количества цифр в числе, работа несколько замедляется. Возможно кому и пригодится. спасибо за внимание!