PrimeNumSieve
ФОРМУЛИРОВКА ЗАДАЧИ:
Найти все простые числа меньше или равные заданному числу N.
ПРОГРАММНЫЙ КОД:
Исходный программный код содержится в файле src\PrimeNumSieve.java.
НАЗНАЧЕНИЕ:
Класс PrimeNumSieve реализует двумя разными по эффективности методами задачу подсчёта всех простых чисел, которые меньше или равны заданному числу N, где:
- метод Eratosthenes реализует алгоритм Эратосфена для подсчёта простых чисел;
- метод EratosthenesWheel реализует комбинацию алгоритмов Эратосфена и так называемого "колесного решета" (wheel factorization) для подсчёта простых чисел;
- метод main реализует консольный интерфейс с пользователем, контролирует доступность необходимого объема памяти, выполняет запуск задач подсчёта простых чисел методами Eratosthenes и EratosthenesWheel, выводит результаты выполнения задач.
АЛГОРИТМ:
Алгоритм Эратосфена сначала помечает в памяти все числа от 1 до N как простые, а затем снимает пометки с заведомо составных чисел вида (i * j), где i = { 2; N ^ (1 / 2) }, j = { i, N / i }. После этого по оставшимся пометкам подсчитывается количество простых чисел. В алгоритме c "колесным решетом" используется решето ограниченного размера "2*3" (по первым двум простым числам), согласно которому все простые числа будут иметь вид 2, 3, (2 * 3) * i - 1, (2 * 3) * i + 1, где i = { 0, N / 6 }. Но т.к. не все числа из этого ряда простые, для их проверки применяется алгоритм Эратосфена. ТАКАЯ КОМБИНАЦИЯ АЛГОРИТМОВ В ОДНОМ МЕТОДЕ ПОЗВОЛЯЕТ ДО 3-Х РАЗ УМЕНЬШИТЬ КОЛИЧЕСТВО ИСПОЛЬЗУЕМОЙ ПАМЯТИ И ПРИ УВЕЛИЧЕНИИ N ПОЛУЧАТЬ СУЩЕСТВЕННЫЙ ВЫИГРЫШ В СКОРОСТИ (ВРЕМЕНИ) ВЫПОЛНЕНИЯ.
СЛОЖНОСТЬ:
Сложность реализованных алгоритмов определяется сложностью алгоритма Эратосфена O(N*log(log N)).
РЕАЛИЗАЦИЯ:
Java version "11.0.1", использованы стандартные возможности JDK.
ОГРАНИЧЕНИЯ:
Приложение контролирует доступность необходимой ему памяти в зависимости от задаваемого пользователем значения N и в случае её нехватки предложит пользователю изменить значение N в сторону уменьшения (на 1% от предыдущего значения N).
ТЕСТИРОВАНИЕ:
Качество тестирования обеспечивалось сравнением и совпадением результатов, получаемых двумя разными алгоритмами при идентичных исходных данных.
КОНТРОЛЬНЫЙ ПРИМЕР выполнения приложения:
<Решето простых чисел> NesioIV, 2022
Введите целое положительное число (не более 2147483647):
1000000000
Вы ввели число 1000000000. Выполняется проверка наличия необходимой памяти...
Проверка наличия необходимой памяти прошла успешно.
Вы ввели число 1000000000. Выполняется подсчёт простых чисел...
ВНИМАНИЕ: ПОДСЧЁТ ПРОСТЫХ ЧИСЕЛ БУДЕТ ВЫПОЛНЕН 2-МЯ РАЗНЫМИ МЕТОДАМИ.
Использованный метод – Eratosthenes
Найдено простых чисел – 50847534
Размер массива памяти,Бт – 1000000000
Время исполнения,мс – 13917
Использованный метод – EratosthenesWheel
Найдено простых чисел – 50847534
Размер массива памяти,Бт – 333333333
Время исполнения,мс – 8485
ВТОРОЙ МЕТОД ИСПОЛЬЗУЕТ МЕНЬШЕ ПАМЯТИ И ВРЕМЯ ЕГО ВЫПОЛНЕНИЯ СТАНОВИТСЯ БОЛЕЕ ЭФФЕКТИВНЫМ С РОСТОМ N.
Process finished with exit code 0