Алгоритм решето эратосфена java

Содержание

Решето Эратосфена, попытка минимизировать память
Реализация алгоритма
Код на java
Решето Эратосфена для поиска простых чисел
Описание алгоритма
Реализация на массиве boolean
Уменьшение количества проверок
Уменьшение объёма памяти
Финальная реализация
Выводы
Решето Эратосфена, попытка минимизировать память
Реализация алгоритма
Код на java
Волшебное решето Эратосфена

Решето Эратосфена, попытка минимизировать память

Одним из алгоритмов для поиска простых чисел является Решето Эратосфена предложенное еще древнегреческим математиком.

Смысл в вычеркивании чисел кратных уже найденным простым. Остающиеся невычеркнутыми в свою очередь являются простыми. Более подробно расписано тут.

Одна из проблем при поиске решетом это объем памяти который надо выделить под фильтруемые числа. Вычеркнутые непростые удаляются уменьшая память, но изначально объем требуется большой.

Для решения используется сегментация (когда память выделяется по кускам) и другие ухищрения (см. тут).

Реализация алгоритма

Алгоритм внизу (написан на java) предполагает минимальный объем памяти — по сути для каждого найденного простого числа мы храним еще одно число — последнее зачеркнутое (наибольшее). Если я правильно оцениваю объем памяти ln(n) — число найденных простых.

Суть алгоритма:

Допустим мы имеем несколько уже найденных простых чисел отсортированных по возрастанию. (Алгоритм стартует с [2,3]). Для каждого из них храним последнее (наибольшее) зачеркнутое число. Инициализируем самими простыми числами.

Выбираем кандидата в простые например наибольшее найденное простое число +1 (в алгоритме внизу перескакиваем четные как заведомо не простые).

Кандидат сравнивается с последним зачеркнутым текущего простого. Пока текущее зачеркнутое меньше кандидата увеличиваем его на текущее простое. Если текущее зачеркнутое равно кандидату, то кандидат не простое число. Выбираем следующего кандидата.

В случае если текущее зачеркнутое больше кандидата, проверяем кандидата на следующем простом числе.

Если добрались до конца списка простых чисел (то есть все зачеркнутые больше кандидата) мы нашли очередное простое число.

Добавляем его в список и инициализируем последнее зачеркнутое найденным простым.

Код на java

import java.util.ArrayList; import java.util.List; public class SieveEratosthenes < static class PrimePair < Integer prime; Integer lastCrossed; PrimePair(Integer prime, Integer lastCrossed) < this.prime = prime; this.lastCrossed = lastCrossed; >> private List primes; private SieveEratosthenes() < primes = new ArrayList<>(); primes.add(new PrimePair(2, 2)); primes.add(new PrimePair(3, 3)); > private void fillNPrimes(int n) < while (primes.size()> private void addNextPrime() < int candidate = primes.get(primes.size()-1).prime + 2; for (int i = 1; i < primes.size(); i++) < PrimePair p = primes.get(i); while (p.lastCrossed < candidate) < p.lastCrossed += p.prime; >if (p.lastCrossed == candidate) < //restart candidate+=2; i=-1; >> System.out.println(candidate); primes.add(new PrimePair(candidate, candidate)); > public static void main(String[] args) < SieveEratosthenes test = new SieveEratosthenes(); test.fillNPrimes(1000); >>

primes = [2, 3] last_crossed = [2, 3] def add_next_prime(): candidate = primes[-1] + 2 i = 0 while i < len(primes): while last_crossed[i] < candidate: last_crossed[i] += primes[i] if last_crossed[i] == candidate: candidate += 2 i = 0 i += 1 primes.append(candidate) last_crossed.append(candidate) def fill_primes(n): while len(primes) < n: add_next_prime() fill_primes(1000) print(primes)

Вся логика традиционных алгоритмов с колесами может быть применена при выборе следующего кандидата.

Возможно это очередное изобретение велосипеда. Готов выслушать замечания.

Источник

Решето Эратосфена для поиска простых чисел

Ранее я уже приводил Алгоритм поиска простых чисел методом перебора делителей. Эта реализация хороша, если вам нужно ровно N первых простых чисел. Но если вы ищете простые числа в некотором диапазоне (скажем, не превосходящие 1 000 000), то лучше воспользоваться более быстрым алгоритмом, который называется «решето Эратосфена».

Описание алгоритма

Этот алгоритм назван в честь древнегреческого учёного Эратосфена Киренского.

Алгоритм заключается в том, что изначально мы берём всё множество целых чисел в интересующем нас диапазоне, от 2 до N. Затем последовательно проходимся по этому множеству, вычёркивая каждое чётное число, т.к. оно делится на 2. После этого возвращаемся в начало и вычёркиваем все числа, делящиеся на 3, если они ещё не зачёркнуты. Затем делящиеся на следующее простое число – на 5. Затем на 7, на 11 и т. д. То есть мы «просеиваем» исходное множество целых чисел через сито. В итоге у нас останутся только простые числа.

Реализация на массиве boolean

Давайте напишем самую простую реализацию этого алгоритма. Метод getAllPrimesLessThan() на вход будет принимать размер решета sieveSize, который ограничивает сверху наш диапазон поиска. Для начала нам нужно создать массив типа boolean. Этот массив и будет нашим ситом. Если значение массива по индексу N равно true – число N простое. Если false – то нет. В начале алгоритма все элементы массива проставляем в true с помощью метода Arrays.fill(). Элементы с индексами 0 и 1 сразу ставим в false, т.к. ни 0, ни 1 не являются простыми числами.

public List getAllPrimesLessThan( int sieveSize) var sieve = new boolean [sieveSize];
Arrays.fill(sieve, true );
sieve[ 0 ] = false ;
sieve[ 1 ] = false ;

Затем в цикле, начиная со второго элемента, проверяем значение каждого элемента. Если элемент равен true, то запускаем вложенный цикл опять же со второго элемента до тех пор, пока произведение индексов i и j не превысит размер массива. И все элементы во вложенном цикле помечаем как false, т.е. они не являются простыми.

В конце ещё раз проходимся по «решету» и собираем простые числа в список:

Данный алгоритм работает раза в 3 быстрее, чем перебор делителей, о котором я писал в прошлой статье. Но его можно ещё ускорить.

Уменьшение количества проверок

Количество проверок можно существенно уменьшить, если проверять не все числа, а только те, квадрат которых не превосходит диапазон поиска. Действительно, если N * N больше, чем размер решета и все возможные числа уже вычеркнуты, то дальше N проверять не имеет смысла.

Ну а вложенный цикл мы начинаем как раз с квадрата этого числа и зачёркиваем каждое число, кратное ему.

Данная оптимизация ускоряет алгоритм почти в 2 раза.

Уменьшение объёма памяти

Наиболее уязвимым местом алгоритма является тот факт, что нам нужно создавать массив под весь диапазон проверяемых чисел, тогда как в методе перебора делителей мы храним только найденные простые числа. На больших диапазонах вам может просто не хватить памяти для создания такого массива.

Но мы помним, что каждый элемент массива имеет булевый тип, т.е. может принимать только 2 значения. Для хранения такой информации достаточно всего 1 бита. То есть 1 байт памяти позволит хранить 8 элементов!

Заменим наш массив на класс BitSet, который позволяет легко оперировать отдельными битами:

var sieve = new BitSet(sieveSize);
sieve.set( 0 , sieveSize - 1 , true ); // изначально все true
sieve.set( 0 , false );
sieve.set( 1 , false );
for ( int i = 2 ; i * i < sieve.length(); i++) if (sieve.get(i)) for ( int j = i * i; j < sieve.length(); j += i) sieve.set(j, false );
>
>
>

Данная реализация работает ещё чуть быстрее предыдущей и почти в 2 раза быстрее изначальной.

Финальная реализация

В итоге наша реализация алгоритма поиска целых чисел с помощью «решета Эратосфена» примет следующий вид:

public List getAllPrimesLessThan( int sieveSize) var sieve = new BitSet(sieveSize);
sieve.set( 0 , sieveSize - 1 , true );
sieve.set( 0 , false );
sieve.set( 1 , false );
for ( int i = 2 ; i * i < sieve.length(); i++) if (sieve.get(i)) for ( int j = i * i; j < sieve.length(); j += i) sieve.set(j, false );
>
>
>

List primes = new ArrayList<>();
for ( int i = 2 ; i < sieve.length(); i++) if (sieve.get(i)) primes.add(i);
>
>
return primes;
>

Оптимизации, которые мы применили:

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

Выводы

«Решето Эратосфена» позволяет искать простые числа в некотором диапазоне в несколько раз быстрее, чем алгоритм перебора делителей. Однако ему требуется точно знать диапазон поиска, а также нужна дополнительная память, чтобы хранить само «решето».

В случае, если диапазон поиска заранее неизвестен или у вас не хватает памяти для хранения решета и скорость поиска при этом не столь критична – используйте метод перебора делителей.

P.S. На написание статьи меня мотивировал пользователь Nik Nikita, который выступил с конструктивной критикой алгоритма перебора делителей на моём канале на YouTube.

Источник

Решето Эратосфена, попытка минимизировать память

Для решения используется сегментация (когда память выделяется по кускам) и другие ухищрения (см. тут).

Реализация алгоритма

Суть алгоритма:

В случае если текущее зачеркнутое больше кандидата, проверяем кандидата на следующем простом числе.

Добавляем его в список и инициализируем последнее зачеркнутое найденным простым.

Код на java

import java.util.ArrayList; import java.util.List; public class SieveEratosthenes < static class PrimePair < Integer prime; Integer lastCrossed; PrimePair(Integer prime, Integer lastCrossed) < this.prime = prime; this.lastCrossed = lastCrossed; >> private List primes; private SieveEratosthenes() < primes = new ArrayList<>(); primes.add(new PrimePair(2, 2)); primes.add(new PrimePair(3, 3)); > private void fillNPrimes(int n) < while (primes.size()> private void addNextPrime() < int candidate = primes.get(primes.size()-1).prime + 2; for (int i = 1; i < primes.size(); i++) < PrimePair p = primes.get(i); while (p.lastCrossed < candidate) < p.lastCrossed += p.prime; >if (p.lastCrossed == candidate) < //restart candidate+=2; i=-1; >> System.out.println(candidate); primes.add(new PrimePair(candidate, candidate)); > public static void main(String[] args) < SieveEratosthenes test = new SieveEratosthenes(); test.fillNPrimes(1000); >>

primes = [2, 3] last_crossed = [2, 3] def add_next_prime(): candidate = primes[-1] + 2 i = 0 while i < len(primes): while last_crossed[i] < candidate: last_crossed[i] += primes[i] if last_crossed[i] == candidate: candidate += 2 i = 0 i += 1 primes.append(candidate) last_crossed.append(candidate) def fill_primes(n): while len(primes) < n: add_next_prime() fill_primes(1000) print(primes)

Вся логика традиционных алгоритмов с колесами может быть применена при выборе следующего кандидата.

Возможно это очередное изобретение велосипеда. Готов выслушать замечания.

Источник

Волшебное решето Эратосфена

Наверняка все, кто читает этот пост не раз использовали, или хотя бы слышали о решете Эратосфена — методе отыскания простых чисел. Сама проблема получения простых чисел занимает ключевое место в математике, на ней основаны некоторые криптографические алгоритмы, например RSA. Есть довольно много подходов к данной задаче, но в этой статье я остановлюсь на некоторых модификациях самого простого из них — решета Эратосфена.
Принцип решета прост: пускай нам нужно отыскать простые числа в промежутке от единицы до некоторого N . Мы заводим массив на N элементов и заполняем его true. Затем последовательно проходим по нему до корня из N, и встречая true, вычеркиваем все числа с этим шагом до N. Алгоритм выглядит компактно и просто, привожу его на языке java.

int primes = new int [P]; // заполняем его простыми до корня из n

boolean sieve = new boolean [n-m+ 1 ]; // вторичное решето

Arrays.fill(sieve, true );

for ( int i= 0 ; i
int h = m % primes[i];

int j = h == 0 ? 0 : primes[i] - h;

for (; j
sieve[j] = false ;

int CACHE = 30000 ; // размер кэша

int M = ( int ) Math .sqrt(N)+ 1 ;

int primes = new int [P]; // массив простых чисел до корня из N

boolean segment = new boolean [CACHE]; // вторичное решето

for ( int I=M- 1 ; I < N; I+=CACHE)
Arrays.fill(segment, true );

for ( int i= 0 ; i < P; i++)
int h = I % primes[i];

int j = h > 0 ? primes[i] - h : 0 ;

for (; j < CACHE; j+=primes[i])

segment[j] = false ;

>

for ( int i= 0 ; i if (segment[i] && (i + I < N))
out .println(i+I); // выводим простое число на экран

>

>

>

Используя этот метод мы очень сильно ускоряем наше решето, практически не усложняя его, для многих задач это ощутимо помогает, например, одна из них: TDPRIMES, на этой задаче можно потренироваться и хорошо увидеть что обычное решето не укладывается в 10с, а сегментированное проходит за 2.8.

Источник