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

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

    1. Arrays.fill(isPrime,true);
    2. isPrime[1] = false;
    3. for (int i=2; i*i < N; i++)
    4.    if (isPrime[i])
    5.       for (int j=i*i; j < N; j+=i)
    6.          isPrime[j] = false;
    7.  


    Алгоритм работает за O(N*log(log(N))), поэтому для небольших чисел он вполне подходит. Рассмотрим случай, когда нам необходимо найти простые числа не от одного до N, а от n до m. Пускай мы имеем ограничения 1 <= m <= n <= 10^9; n-m <= 10^6. Здесь нам необходимо применить алгоритм, называемый двойным решетом. Он заключается в том чтобы найти простые числа до корня из n, затем сохранить их в отдельный массив и точно так же «вычеркивать» эти простые числа с определенным шагом, но уже из необходимого нам промежутка [m, n]. Кратко этот алгоритм будет выглядеть так:

    1. int primes = new int[P]; // заполняем его простыми до корня из n  
    2. boolean sieve = new boolean[n-m+1]; // вторичное решето  
    3. Arrays.fill(sieve, true);
    4. for (int i= 0; i<P; i++) {
    5.    int h = m % primes[i];
    6.    int j = h ==  0 ?  0 : primes[i] - h;
    7.    for (; j<=n-m; j+=primes[i])
    8.       sieve[j] = false;
    9.  


    Так можно справляться с диапазонами, достаточно удаленными от нуля. Теперь подходим к самому интересному моменту: а что, если нам необходимо вывести простые числа от 0 до N = 10^8? Если вспомнить асимптотику, то это на первый взгляд кажется реальным даже для обычного решета, но посмотрев на затраты памяти: 10^8 * 4 = 400МБ мы видим что задача не такая тривиальная, особенно, если у нас есть жесткие временные ограничения. Для решения этой задачи можно выделить два подхода, а именно:
    • упаковка решета
    • учитывание кэш-памяти

    Рассмотрим их немного подробнее. Упаковка заключается вот в чем: в современных языках программирования тип boolean занимает в среднем от одного до четырех байт, хотя его можно закодировать всего одним битом. Поэтому мы можем создавать массив целых чисел и работать с каждым из них как с побитовой маской, тем самым экономя память в 8-30 раз. Преимущества видны сразу, но теперь остановимся чуть подробнее на второй идее, которая гарантированно ускоряет решето в несколько раз
    Многим известно, что в нашем компьютере между процессорной и оперативной памятью находится кэш-память, работа с ней проводится намного быстрее, чем с оперативной, но ее размеры ограничены. Например, при работе с большим массивом, процессор загружает в кэш некоторую его часть, работает с ней, потом переносит обратно в оперативную, загружает другую и так далее. А теперь вспомним наш алгоритм решета: каждое простое число мы вычеркивали из всего массива, проходясь по нему от начала до конца. Поэтому процессор много раз будет загружать в кэш разные отрезки массива и скорость на этом будет сильно теряться. Данный подход предлагает минимизировать затраты на копирование массива из одной памяти в другую. Это сделать несложно если весь наш промежуток разделить на кусочки, до 3*10^4 элементов, что приблизительно равно размеру кэша и работать с ними по-порядку. Тогда мы за минимальное количество загрузок разберемся со всем массивом. Примерно так это будет выглядеть:

    1. int CACHE = 30000; // размер кэша  
    2. int M = (int)Math.sqrt(N)+1;
    3.  
    4. int primes = new int[P]; // массив простых чисел до корня из N  
    5. boolean segment = new boolean[CACHE]; // вторичное решето  
    6. for (int I=M-1; I < N; I+=CACHE) {
    7.         Arrays.fill(segment, true);
    8.         for (int i= 0; i < P; i++) {
    9.             int h = I % primes[i];
    10.             int j = h >  0 ? primes[i] - h :  0;
    11.             for (; j < CACHE; j+=primes[i])
    12.                 segment[j] = false;
    13.         }
    14.         for (int i= 0; i<CACHE; i++) {
    15.             if (segment[i] && (i + I < N)) {
    16.                 out.println(i+I); // выводим простое число на экран  
    17.             }
    18.         }
    19. }



    Используя этот метод мы очень сильно ускоряем наше решето, практически не усложняя его, для многих задач это ощутимо помогает, например, одна из них: TDPRIMES, на этой задаче можно потренироваться и хорошо увидеть что обычное решето не укладывается в 10с, а сегментированное проходит за 2.8.
    Поделиться публикацией
    Комментарии 35
      +3
      Подсветку кода бы еще, а так за статью спасибо, будет, что рассказать=)
        0
        Подскажите нормальный сайтик, на котором это можно будет сделать, что бы хабровский типограф не порезал половину — сделаю.
        А то я пытался и получается какая-то фигня.
        Пытался через tohtml.com/java/
          +1
          Так, с подсветкой разобрались.
          0
          Как решить вопрос с переключением контекстов в многозадачных операционных системах? Ведь при их переключении бОльшая часть кеша заполняется совсем другими данными.
            +1
            Ну на самом деле криптография использует решето Аткина. И основной проблемой является все таки определение является ли это число простым. Эта проблема решена для чисел Мерсена и чисел Ферма, но тест простоты для других чисел обладает высокой сложностью.
              0
              Цель статьи обучающая, как простыми инструментами добиться приемлемых результатов. Эратосфен не претендует на первенство, но он прост и понятен, чаше всего в небольших задачах этого достаточно.
              • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Спасибо кэп. В этом то и вся проблема, с помощью вероятностных алгоритмов нельзя строго доказать простоту числа.
                    0
                    в случае, когда важно быстродействие, да, лучше использовать тест миллера-рабина.
                    но если я знаю, что числа небольшие, я буду использовать решето.
                    0
                    Алгоритм AKS, являющийся детерминированным и полиномиальным, написанный на Java:
                    для 100 бит отрабатывает за три секунды
                    для 150 бит — за 7 секунд
                    для 200 бит — за 23 секунды
                    для 250 бит — за 35,5 секунды
                    далее экстраполируйте сами :)

                    Core i7 920 2,6GHz
                      0
                      Да он просто не рюхает. Основная проблема — разложение числа на множители.
                    0
                    Лучше реализовать на битовом массиве — минимальное потребление памяти.
                      0
                      А почему вообще существует эта проблема? Разве еще не нашли все простые числа до какого-нибудь безумного числа? Вон, число Пи регулярно каким-нибудь энтузиастом пересчитывается до какой-то нереальной, все возрастающей точности.
                        0
                        Множество цифр числа Пи и множество простых чисел бесконечны. Ведутся работы по доказанию гипотезы о возможной конечности последовательности простых близнецов и чисел Софи Жермен.
                          0
                          Это понятно, что бесконечны. Но для практического применения, наверное, используется не бесконечное множество. Разве это множество еще не найдено?
                            0
                            Что касаемо числа Пи, то для абсолютного большинства практических задач такой точности не нужно. И я, честно говоря не вижу большого смысла в уточнении этого числа. Разве что как сомнительный источник случайной последовательности.
                            Простые же числа более интересны. Во первых, не все гипотезы связанные с ними доказаны, во вторых большие простые числа активно используются в гражданской криптографии (RSA, алгоритм Диффи-Хеллмана) и думаю применяются еще в дюжине достаточно узких направлений математики.
                              0
                              Все это прекрасно, но Вы, простите, кому и на какой вопрос сейчас ответили?
                                0
                                Эмм… Постарался на ваш.
                                Для большинства практических задач необходимые точности были получены еще несколько веков назад. Однако существуют и будут существовать направления, где нужны будут очень большие числа или точности.
                                  0
                                  По-моему, Вы все-таки не мне отвечаете.

                                  Я спросил — найдены ли уже простые числа до некоего максимального, ныне применяемого?

                                  Вы ответили — сначала — что простые числа интересны, что не все теории про них доказаны и что они применяются в разных областях. Здорово. Но это не ответ на вопрос «найдены ли числа».

                                  Теперь Вы отвечаете — существуют направления, где нужны большие числа. Но это опять не ответ на вопрос «найдены ли числа».

                                  Может, Вас сбило с толку упоминание числа Пи? Понимаете, я не спрашивал, где все эти числа применяются и зачем они вообще нужны. Я спрашивал — найдены ли нужные на сегодняшний день числа?
                                    0
                                    В первом комменте я ответил что их бесконечно много. И как следствие найти максимальное такое число нельзя. Нельзя взять и сказать: «А знаете нам пожалуй этого числа хватит, давайте перестанем искать и назовем его максимальным».
                                    Или я опять не понимаю вашего вопроса? Если так объясните что значит «нужные числа»? =)
                                      0
                                      Я знаю, что их бесконечно много. Я спросил, цитирую: «Но для практического применения, наверное, используется не бесконечное множество. Разве это множество еще не найдено?»

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

                                      Как еще нужно переформулировать? Может, пример привести? Например: таблица умножения уже давно составлена, все знают, что пятью-пять будет двадцать пять и никто не сидит и не пересчитывает на пальцах, сколько это будет. Все нужные для жизни значения таблицы найдены и спокойно используются.

                                      Так вот вопрос — что, простые числа еще на намолотили на суперкомпьютерах до нужного количества?
                                        +1
                                        Итак как и отвечал выше, для большинства задач того что сейчас есть вполне достаточно. Например в практической реализации алгоритма Диффи-Хеллмана (генерация общего секретного ключа без передачи его по каналам связи) советуется использовать числа порядка от 10^100 до 10^300. Очевидно, что ни одна нормальная программа не будет таскать с собой архив всех таких простых чисел (банально не хватит места) и генерирует их каждый раз заново. Т.е. таблицы простых чисел, как таковые, я полагаю, нигде не используются (разве, что в «спец-проектах»).
                                        А достаточно конечно не намолотили, более того существуют достаточно внушительные денежные премии для энтузиастов-молотильщиков =).
                                          0
                                          Ага, ну вот теперь понятно, спасибо.
                              +1
                              Для практического применения используется (на текущий момент) множество почти всех простых чисел размером до 4 тысяч бит (на число). При этом списка этих самых простых чисел ни у кого нет — их генерация и/или поиск начинается заново для каждого нового ключа шифрования.

                              Найти и составить список не получится по той причине, что не хватит места для записи даже для битовой маски — 2^4096 бит = 2^4092 байт = 4052 Тбайт.
                                0
                                То ли я чего-то не понял, то ли Вы чего-то не так посчитали. Битовая маска займет именно 4 тысячи бит. А 4052 Тбайт — это как раз объем всех чисел от нуля до четыретысячибитного, включая и не_простые. Простых будет существенно меньше.
                                  0
                                  Битовое решето будет содержать столько бит, сколько чисел нам нужно обработать.

                                  Битовые маски отдельных чисел не используются для поиска простых (почти).
                                    0
                                    А! Это была другая маска. Тогда понятно.
                          –1
                          Я когда-то давным давно еще в школьные годы использовал массив типа boolean в паскале на олимпиадах, что давало нереальный прирост скорости выполнения задач с простыми числами. Почему-то заполнить массив значениями true и false занимало считанные секунды, а вот вычисление, является ли конкретное число простым по другим алгоритмам было весьма долгим процессом.
                          В итоге у меня любые задачи класса «найти все такие простые числа, что..» выполнялись молниеносно, а у конкурентов вылетали за отведенное время.

                          Причины этого феномена я так и не изучил, а сейчас уже и поздно как-то, но к решету Эратосфена с тех пор отношусь с большим уважением.
                            0
                            Это весьма неудивительно — проверка числа на простоту длится sqrt(n), значит N чисел проверятся за O(N*sqrt(N)).

                            В то время как грамотное решето работает O(N), примитивное — как описано в статье, O(Nlog(log(N))). Для миллиона — разница в 1000 раз для грамотного и в 231 — для простого.
                              0
                              а вы не подскажете случайно какой алгоритм грамотный? Вообще очень заинтересовала тема алгоритмов, есть ли какая то литература именно по подобным численным алгоритмам? Не нашел подобного в книгах Кормена, Седжвика… и других классических книг по алгоритмизации.
                            0
                            если присмотреть в коде обнаруживается огромное количество ошибок, начиная с некоторых имен переменных которые сначала называются M а потом P, и кончая OutOfRange ошибками работы с массивами. Поправьте плиз чтобы было работоспособно.
                              0
                              Посмотрим на первый код. Говорят, что он нужен для того, чтобы найти простые до N <= 10^6. В таком случае в строке for (int j=i*i; j < N; j+=i) будет ошибка, так как j переполниться.
                                0
                                Вы ошибаетесь. j не будет больше 101 000.
                                0
                                нет смысла разбирать ошибок слишком много… не важно… будем считать что человек хотел показать суть алгоритма
                                  0
                                  Код исправил.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое