Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии

    (Источник рисунка )

    Общеизвестно, что Решето Эратосфена (РЭ) один из древнейших алгоритмов, появившийся задолго до изобретения компьютеров. Поэтому можно подумать, что за века этот алгоритм изучен вдоль и поперек и добавить к нему ничего невозможно. Если посмотреть Википедию – там море ссылок на авторитетные источники, в которых запросто утонуть. Поэтому удивился, когда на днях случайно обнаружил, что вариант, который в Википедии преподносится как оптимальный, можно заметно оптимизировать.

    Дело было так. В обсуждении статьи по функциональному программированию (ФП) задал вопрос: как в этой парадигме написать РЭ. Обладая более чем скудными знаниями по ФП, не берусь судить об ответах, но другие участники обсуждения забраковали некоторые из предложенных сходу решений, указав, что вместо теоретической сложности

    $O(n \log \log n)$ (1)

    предложенная реализация будет обладать вычислительной сложностью

    $O(n^2/\log n) $ (2)

    и что с такой сложностью не дождаться, когда, например, просеются 10 миллионов чисел. Мне стало интересно и я попробовал реализовать оптимальную согласно Википедии версию, используя привычное мне процедурное программирование. В Delphi-7 у меня получился следующий код:

    Листинг 1
    program EratosthenesSieve;
    // Sieve of Eratosthenes
    {$APPTYPE CONSOLE}
    
    uses
      SysUtils, DateUtils,Math;
    const
     version ='1.0.1d1';
     N = 1000000000; // number of primes
    var
     sieve : array [2..N] of boolean; // false if prime
     t0, t1,dt : TDateTime;
     O,C : Extended;
    
    procedure init;
      var
       i : integer;
      begin
       for i:=2 to n do
        sieve [i] := false;
      end; //init
    
    procedure calc (start : integer);
      var
       prime, i : integer;
       breakLoop, exitProc : Boolean;
      begin
       prime := start;
       exitProc := false;
       repeat
    // find next prime
          prime := prime+1;
          while (prime<N) and sieve[prime] do
           inc (prime);
          i:= sqr(prime);
    // delete
          if i<= N then
            begin
              breakLoop := false;
              repeat
                if i<= N then
                 begin
                  sieve [i] := true;
                  inc (i,prime);
                 end
                else  // if i<= N
                 breakLoop := true;
              until breakLoop;
            end  
          else // if prime+prime<= N
           exitProc := true;
       until exitProc;
      end; //calc
    
    procedure print;
      var
        i :integer;
        found : integer;
    
      begin
        found := 0;
        for i:=2 to N do
         if not sieve [i] then
          begin
    //       write (i,', ');
            inc(found);
          end;
        writeln;
        writeln ('Found ',found,' primes.');
      end; //
    
    begin // program body
      writeln ('Sieve of Eratosthenes version ', version);
      writeln('N= ',N);
    
      init;
      t0 := now;
      writeln('Program started ',DateTimeToStr(t0));
      t0 := now;
      calc (1);
      t1 := now;
      writeln('Program finished ',DateTimeToStr(t1));
      dt := SecondSpan(t1,t0);
      writeln ('Time is ',FloatToStr(dt),' sec.');
    
      O := N* ln(ln(N));
      C := dt/O;
      writeln ('O(N ln ln N)= ',O,' C=',C);
    
      O := sqr(N)/ln(N);
      C := dt/O;
      writeln ('O(N*N/ln N)= ',O,' C=',C);
    
      print;
      
      writeln ('Press Enter to stop...');
      readln;
    end.


    РЭ представлено булевым массивом sieve с инверсными значениями — если число простое, оно обозначается как false, что позволяет сократить количество операций отрицания (not) при просеивании. В программе 3 процедуры: инициализации РЭ — init, вычислений (просеивание и зачеркивание чисел в РЭ) — calc и вывода найденных в результате простых чисел — print, при этом подсчитывается количество найденных чисел. Особо обращу внимание на закомментированный вывод простых чисел в процедуре print: для тестирования при N=1000 комментарий снимается.

    Здесь в процедуре calc использую рекомендацию Википедии: для очередного простого числа i вычеркивать из РЭ числа

    $i^2, i^2+i, i^2+2i, …$



    Эта программа просеяла миллиард чисел за 17.6 сек. на моем ПК (CPU Intel Core i7 3.4 ГГц).
    Сделав эту программу, я вдруг вспомнил о широко известных свойствах четных и нечетных чисел.

    Лемма 1. 1) нечетное+нечетное=четное; 2) нечетное+четное=нечетное; 3) четное+четное= четное.

    Доказательство

    1) $(2n+1)+(2m+1)=2n+2m+2 $делится на 2. ЧТД.
    2)$ (2n+1)+(2m)=2n+2m+1$ не делится на 2 без остатка. ЧТД.
    3)$ (2n)+(2m)=2n+2m$ делится на 2. ЧТД.

    Лемма 2. Квадрат нечетного числа есть нечетное число.
    Доказательство. $(2n+1)^{2}=4n^{2}+4n+1$ не делится на 2 без остатка. ЧТД.

    Замечание. Простое число, большее 2, нечетное.

    Поэтому можно вычеркивать только нечетные числа:

    $i^2, i^2+2i, i^2+4i, … $ (3)

    Но прежде надо вычеркнуть все четные числа. Это делает измененная процедура инициализации init.

    Листинг 2
    program EratosthenesSieve;
    // Sieve of Eratosthenes
    {$APPTYPE CONSOLE}
    
    uses
      SysUtils, DateUtils,Math;
    const
     version ='1.0.1d1';
     N = 1000000000; // number of primes
    var
     sieve : array [2..N] of boolean; // false if prime
     t0, t1,dt : TDateTime;
     O,C : Extended;
    
    procedure init;
      var
       i : integer;
      begin
       for i:=2 to n do
        sieve [i] := not odd(i); 
      end; //init
    
    procedure calc (start : integer);
      var
       prime,prime2, i : integer;
       breakLoop, exitProc : Boolean;
      begin
       prime := start;
       exitProc := false;
       repeat
    // find next prime
          prime := prime+1;
          while (prime<N) and sieve[prime] do
           inc (prime);
    //      i:= prime*prime;
          i:= sqr(prime);
          prime2 := prime+prime;   
    // delete
          if i<= N then
            begin
              breakLoop := false;
              repeat
                if i<= N then
                 begin
                  sieve [i] := true;
                  inc (i,prime2);
                 end
                else  // if i<= N
                 breakLoop := true;
              until breakLoop;
            end  
          else // if prime+prime<= N
           exitProc := true;
       until exitProc;
       sieve [2] := false;
      end; //calc
    
    procedure print;
      var
        i :integer;
        found : integer;
    
      begin
        found := 0;
        for i:=2 to N do
         if not sieve [i] then
          begin
    //      write (i,', ');
            inc(found);
          end;
        writeln;
        writeln ('Found ',found,' primes.');
      end; //
    
    begin // program body
      writeln ('Sieve of Eratosthenes version ', version);
      writeln('N= ',N);
    
      init;
      t0 := now;
      writeln('Program started ',DateTimeToStr(t0));
      t0 := now;
      calc (2);
      t1 := now;
      writeln('Program finished ',DateTimeToStr(t1));
      dt := SecondSpan(t1,t0);
      writeln ('Time is ',FloatToStr(dt),' sec.');
    
      O := N* ln(ln(N));
      C := dt/O;
      writeln ('O(N ln ln N)= ',O,' C=',C);
    
      O := sqr(N)/ln(N);
      C := dt/O;
      writeln ('O(N*N/ln N)= ',O,' C=',C);
    
      print;
      
      writeln ('Press Enter to stop...');
      readln;
    end.


    Эта программа сработала за 9.9 сек. – почти вдвое быстрее.

    Для оценки соответствия реального времени работы программы теоретическому я предположил, что

    $dt=C*O,$



    где $dt$ – измеренное время работы;
    $C $– константа с размерностью времени;
    $O$ – теоретическая оценка.

    Вычислил отсюда $C $ для оценки (1) и (2). Для $N= 10^6$ и меньше $dt$ близко нулю. Поэтому привожу данные по первой программе для больших $N.$

    $N $ (1) (2)
    $10^7 $ $1.69\cdot 10^{-9} $ $2.74\cdot 10^{-9}$
    $10^8 $ $5.14 \cdot 10^{-9}$ $1.47 \cdot 10^{-8}$
    $10^9$ $5.80 \cdot 10^{-9}$ $1.29 \cdot 10^{-7}$

    Как видим, оценка (1) гораздо ближе к реальным результатам. Для второй программы наблюдается похожая картина. Сильно сомневаюсь, что открыл Америку с применением последовательности (3) и буду очень благодарен за ссылку на работу, где применялся этот подход. Скорее всего, авторы Википедии сами утонули в море информации по РЭ и пропустили эту работу.

    PS О приведенном в Википедии алгоритме с «линейным временем работы» см.
    Поделиться публикацией

    Похожие публикации

    Комментарии 139

      +2
       N = 1000000000; // number of primes
      var
       sieve : array [2..N] of boolean; // false if prime

      Волшебно! :) Выкинуть гигабайт памяти непонятно на что :)

      Что-то мне подсказывает, что бинарное дерево простых чисел будет занимать радикально меньше памяти.

      Как обычно, нужно принимать во внимание не только вычислительную сложность алгоритма, но еще и сложность по памяти. И если миллиард итераций для современных камней — это нормально, то гигабайт памяти на вспомогательную структуру данных — явный перебор.
        +1
        Как обычно: что нужно — на то и кидаем: нужно ускорить — не постоим за памятью, нужно комнату обогреть камень догрузить — подождем с обеда до обеда :) В вики, нпр., ссылки, где простоту каждого числа 1 битом кодируют…
          –1
          Как обычно: что нужно — на то и кидаем: нужно ускорить — не постоим за памятью,

          А тут еще вопрос, насколько поиск по бинарному дереву тормознее. Да, это лишний log n. Но для миллиарда — это плюс-минус 30 сравнений. А по памяти экономия колоссальная.

          В вики, нпр., ссылки, где простоту каждого числа 1 битом кодируют…

          Хотя бы. Вы тут от 8 до 32 раз потребление памяти уменьшите. Но скорость несколько уменьшится.
            0
            А тут еще вопрос, насколько поиск по бинарному дереву тормознее.
            Я не спорю, тем более, что сам очень люблю использовать деревья (вообще графами занимаюсь :) Попробуйте реализовать этот поход в программе — тогда будет возможно количественное сравнение.
            +1
            Может быть, будет интересно — написал реализацию решета на Swift. Собственно «решето» — три строчки в цикле while, включая условие выхода.
            0
            ну а как вы обходить то это дерево будете? и изначально в нём должны быть все числа. весь миллиард.
            вы алгоритм эратосфена-то видели? бинарное дерево может быть хорошо для записи результата работы алгоритма. но при работе он потребует памяти.
              0
              ну а как вы обходить то это дерево будете?

              Бинарным поиском.

              и изначально в нём должны быть все числа. весь миллиард.

              Зачем? Вы в дерево можете добавлять элементы динамически. Да, балансировка дерева — это затраты времени. Вопрос в том, что чем больше числа, тем реже будут попадаться простые, соответственно перестройка дерева — относительно редкая операция.

              вы алгоритм эратосфена-то видели?

              Видел. И что? Ну а если вы захотите триллион простых чисел найти, сразу же терабайт памяти выделять будете? И гарантированно уроните домашнюю систему, и среднестатистический сервер? Или все же будете думать о тех проблемах, которые у вас возникнут? массив и дерево — эквивалентные представления одной и той же структуры данных. А вот свойства их сильно разные. Дерево — занимает ровно столько памяти, сколько необходимо. При этом сложность поиска — логарифмическая. Что не страшно даже для размерностей в триллион.

              бинарное дерево может быть хорошо для записи результата работы

              Напротив, дерево занимает минимум памяти. И результат работы алгоритма — это еще вопрос, какой должен быть. В консоль весь перечень чисел вы будете выплескивать только на лабораторках в ВУЗе/школе. В реальной работе будут какие-либо вменяемые структуры данных. Список? Дерево? Хэш-таблица? Зависит от потребностей.
                0
                Видел. И что?

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

                если задача будет стоять найти их с помощью алгоритма эратосфена — то да, буду выделять. Ну либо бить на части и искать там. потом объединять. но двоичное дерево сюда не лезет. покажите как.
                  +2
                  Вы не могли бы накидать алгоритм, как можно решето эратосфена на двоичном дереве сделать?

                  Точно также, как и на массиве, но вместо
                  sieve[i]
                  будете писать
                  getSieve(i)
                  . Функция getSieve(idx) будет вам возвращать true, если число — простое, и false — В противном случае.

                  если задача будет стоять найти их с помощью алгоритма эратосфена — то да, буду выделять.

                  Сильно. Т.е. вас не будет смущать, что, программа у вас тупо вылетит по out of memory exception? И при этом, я вам привел простой путь, как можно разменять память на скорость.

                  если задача будет стоять найти их с помощью алгоритма эратосфена

                  Студент? :) На практике у вас не будет стоять задача найти ИМЕННО с помощью такого-то алгоритма. На практике у вас будет задача — РЕШИТЬ задачу корректно и с учетом разумных ограничений по памяти/скорости + доп. ограничения предметной области.
                    0
                    На практике часто стоит задача оценки производительности (benchmark), и для нее часто используют РЭ в различных вариантах часто сознательно загружая ОЗУ.
                      0
                      часто сознательно загружая ОЗУ.

                      Вам тут очень легко перестараться: размер ОЗУ вы можете узнать у операционки, а вот фрагментацию ОЗУ вы уже не узнаете просто так. Да и еще непонятно, что операционка будет делать с вашими страницами памяти. Возьмет и отправит в своп. И весь ваш бенчмарк слился. Кстати, не могу сказать, что задача оценки производительности стоит «часто».
                        0
                        Кстати, не могу сказать, что задача оценки производительности стоит «часто».
                        Зависит от специфики работы.
                        Возьмет и отправит в своп. И весь ваш бенчмарк слился.
                        Бенчмарк нужен и для выявления возможности таких накладок. Когда подобное недопустимо меняют конфигурацию или систему.
                          0
                          Вряд ли бенчмарк будет одним здоровым куском выделять память. Скорее, это будут порции памяти разумного размера.
                            0
                            И это м.б. целью тестирования: как выделяет, насколько быстро и т.д.
                              0
                              И это м.б. целью тестирования: как выделяет, насколько быстро и т.д.

                              В таком случае, это будет тест ядра операционной системы, а не железа/приложения. возможно и реальная задача, но явно не распространенная. Насколько я разбираюсь в колбасных обрезках, обычно нужно протестировать производительность своего разработанного софта. И тут уже не решето Эратосфена применяют, а имитируют нагрузку пользователей. При чем, стараются угадать реальные кейсы.
                                0
                                обычно нужно протестировать производительность своего разработанного софта
                                Не только. Но, нпр., новые рабочие места. Или сервер. Или кластер. Или бортовую систему. — Для кого обычно, а для других не очень обычно.
                      +3
                      Точно также, как и на массиве, но вместо sieve[i]

                      Ну и? первый проход вычеркивает все четные числа. соответственно в ваше дерево должны будут быть они занесены изначально, весь миллиард (если вычеркиваем), или пол-миллиарда добавлено, если мы в дереве храним вычеркнутое.
                      будет ли дерево с таким количеством узлов меньше жрать памяти чем массив — для меня ясно. нет, не будет.
                      далее — последовательный доступ к памяти по сравнению со случайным в дереве — в разы быстрее.

                      если памяти мало — общий диапазон разбивается на под-диапазоны и решето применяется последовательно.

                      И при этом, я вам привел простой путь, как можно разменять память на скорость.

                      а вас именно об этом просили? нет, правда? если мне нужно менять память на скорость — в пределе вообще одним числом можно обойтись и делить до корня из лимита. да, не быстро будет, но зато драгоценную память не потребим.
                      Студент? :)

                      ай спасибо за комплимент. как я оказывается хорошо сохранился. а вы я так понимаю — преподаватель?

                      На практике у вас будет задача — РЕШИТЬ задачу корректно и с учетом разумных ограничений по памяти/скорости

                      вот и стоит задача — решить как можно быстрее. и вас не удивляет, что лучший результат www.spoj.com/problems/PRIMES2 достигнут на решете на массиве. а не на супер-пупер дереве.

                        0
                        если памяти мало — общий диапазон разбивается на под-диапазоны и решето применяется последовательно.

                        Тьфу-ты, бес попутал :) Прошу пардону. :) Действительно, вся соль решета Эратосфена в потреблении кучи памяти. И хоть какой-то разумный выход — действительно бить большой диапазон на более мелкие.
                        Но это как раз и говорит о том, что нужно думать, что пишешь: выделить массив на гигабайт просто в качестве примера — это сильно. Если речь идет о таких числах, значит изначально нужно продумывать либо менее требовательный к памяти алгоритм, либо бить задачу на куски.
                        Тоже самое и про терабайт памяти. Хрен вы его выделите одним куском.
                          +1
                          Тьфу-ты, бес попутал :)

                          не проблем :-) а то я уж думал, что сам в маразм впал и чего-то простейшего, что все легко видят не ухватил.

                          Тоже самое и про терабайт памяти. Хрен вы его выделите одним куском

                          В win x64 VA для процесса 8TB. И максимальный лимит на swap файл 16TB. т.е. выделить можно. правда всё будет в swap на обычных машинах и при работе решета последовательно будет с диска в память и обратно трешиться, но, в принципе, на домашнем компе на сегодняшний день — можно. непрактично, очень не быстро, но можно. не нужно, это да, но можно.
                            0
                            в принципе, на домашнем компе на сегодняшний день — можно
                            Разве речь в статье только о домашних ПК? Можно и о супер-компах заботу проявить ;)))
                              0
                              Разве речь в статье только о домашних ПК? Можно и о супер-компах заботу проявить ;)))

                              У вас на суперкомпах память быстрее кончится, чем вычислительные возможности. Ну, например, 256Гб памяти — это уже где-то ближе к верхней планке. При этом, этим алгоритмом ее сожрать можно очень быстро.
                                0
                                Супер-компы быстро развиваются…
                              0
                              В win x64 VA для процесса 8TB. И максимальный лимит на swap файл 16TB. т.е. выделить можно

                              Но то, что оно именно ВЫДЕЛИТСЯ — далеко не факт :) Т.е. вероятность заработать out of memory exception — очень и очень повышается.

                              не нужно, это да, но можно.

                              Именно с этого я и начал, пока в маразм не ушел :) Часто вижу, как свежедипломированные специалисты подобными вещами в реальных проектах начинают чудить. А все почему? Потому что 4-6 лет в ВУЗе, если не пьянку пьянствовали, то решали только учебные задачи.
                              Меня, например, порадовало, как один краснодипломник на тестовом задании в цикле коннекшн к базе устанавливал. Ну там, цикл по количеству элементов в коллекции. На каждой итерации: а) создаем ADO DB com-объект, устанавливаем коннекшн, выполняем запрос.
                              Вопрос был только один: почему диплом — красный. :)
                                0
                                Вопрос был только один: почему диплом — красный.

                                ну наверное как в анекдоте don-ald.livejournal.com/541672.html
                                что бы опасались…

                                Но то, что оно именно ВЫДЕЛИТСЯ — далеко не факт :)

                                почему? я завтра если время будет добавлю свопа и попробую тер выделить и пройтись по нему. консольная прога, с.с++ win10. результат отпишу.
                                  0
                                  я завтра если время будет добавлю свопа

                                  Так не честно :)

                                  пройтись по нему. консольная прога, с.с++ win10. результат отпишу

                                  А винт, случаем, не SSD?
                                    +1
                                    ну вот, получилось следующее: свопа добил до 905GB — на 2х SSD и одном HDD (больше места просто нет) плюс 32GB рамы.
                                    Попробовал аллоцировать вектор на 900GB — не вышло.
                                    Попробовал на 100GB — вышло и committed памяти было 105GB. В общем понятно, что запас нужен. проверил два прохода:
                                    Allocated in 153479ms << время на std::vector test(size);
                                    First pass in 228883ms << проход по вектору с занулением 0x00FF00FF00FF00FF — имитируем вычеркивание четных
                                    Second pass in 314308ms << проход с шагом 3 побайтовый

                                    Попробовал с 800GB — выделило, committed memory 840GB. Ждать окончания выполнения на 800GB уже не стал.

                                    Резюме — на современных машинах можно работать с терабайтными массивами, но медленно. лучше разбить их на части, которые лезут в память. а идеально в кеш первого уровня :-)
                                      0
                                      Интересный тест. Кстати, а вектор гарантирует наличие непрерывного куска памяти? Или все же выделяет ее кусочками? Вообще, в теории, у операционки блок какого максимального размера можно запросить?
                                        0
                                        да, стандарт гарантирует. у Win операционки x64 процессу можно запросить 8TB минус накладные расходы (код, стек, BSS, рантайму памяти надо). Но если на асме примитивное консольное приложение накорябать — то почти все 8TB получатся. Линукс вроде 128TB может процессу выделить.
                                          +1
                                          Да, С++ вектор гарантирует непрерывный кусок памяти.

                                          Операционке в общем без разницы какой блок выделять. Благодаря MMU, то что для процесса выглядит как один большой регион, на самом деле может быть размазано тонким слоем по памяти и свопу. Так что вопрос чисто к имплементации, которая, естественно может отличаться на разных версиях ядра, не говоря уж о разных ядрах.
                                    0
                                    Слышал об обратном случае преувеличенной заботы о ресурсах. Во времена IBM PC AT в редакцию одного солидного н-т. журнала серьезные вроде бы авторы прислали описание своей прикладной программы, где особой заслугой отмечалась реализация обработки событий мыши на ассемблере. На недоуменный вопрос редактора, а почему на ассемблере, было уверенно отвечено, что на высоком ЯП быстродействия может не хватить. В редакции, когда обсуждали, кто-то предположил, что может они не рукой мышь двигают, а из пневмопушки ей стреляют, чтобы катилась быстрей.
                                    0
                                    на самом деле можно реализовать решето с помощью дерева, просто будет немного обратная логика: изначально дерево пустое, а добавляться туда будут только НЕ простые элементы. Конечно никакого выигрыша это не даст, т.к. как раз НЕ простых достаточно много.
                                    Ну и на самом деле, такое решето — не самый оптимальный алгоритм. Есть более оптимальный по времени и памяти (не новый алгоритм, а доп. оптимизации). Ссылка: www.e-maxx-ru.1gb.ru/algo/eratosthenes_sieve
                                    Есть более оптимальный по асимптотике алгоритм на основе решета, который работает значительно быстрее не оптимизированного решета и примерно также, как оптимизированный + находит для каждого числа его наименьший простой делитель, но требует больше памяти. Ссылка: www.e-maxx-ru.1gb.ru/algo/prime_sieve_linear
                                      0
                                      на самом деле можно реализовать решето с помощью дерева
                                      Можно. Реализуйте. А сообщество здесь обсудит, как Вам это удалось ;)
                                      Есть более оптимальный по времени и памяти (не новый алгоритм, а доп. оптимизации). Ссылка
                                      Эту ссылку уже приводили в этом обсуждении — воспользуйтесь поиском по странице.
                                      Есть более оптимальный по асимптотике алгоритм на основе решета, который работает значительно быстрее не оптимизированного решета и примерно также, как оптимизированный + находит для каждого числа его наименьший простой делитель, но требует больше памяти.
                                      И этот алгоритм здесь обсуждали. Работает он медленнеее и по асимптотике доказательство здесь не закончено. Более того эксперимент вызывает сомнения в оценке — я выложу позже результаты.
                                        0
                                        И этот алгоритм здесь обсуждали. Работает он медленнеее и по асимптотике доказательство здесь не закончено.

                                        Ну если доказательство, которое я привел в другой ветке — не закончено, то я не знаю уже.


                                        Работает он медленее на небольших n именно из-за большего в 32 раза потребления памяти. На больших n (теоретически) он будет работать быстрее, но там для таких больших n уже с оперативной памятью проблемы начнутся.


                                        Прелесть (кроме ассимтотики) этого алгоритма в том, что помимо простых чисел автоматом получается возможность быстро раскладывать на простые множители все числа до n.

                                          0
                                          К сожалению, у меня не было достаточно времени, чтобы все это обдумать, но т.к. заданы вопросы — отвечу предварительными впечатлениями.
                                          если доказательство, которое я привел в другой ветке — не закончено, то я не знаю уже.
                                          По доказательству произошла путаница в обозначениях: м.б. я сам запутался, а м.б. Вы меня запутали — с мат. точки зрения это не важно, важно, что ни я, ни другие участники обсуждения пока по Вашему доказательству категорически не высказались. Я думал, что может Вы внесете поправки, а Вы м.б. думали, что я сделаю указанные Вами замены:
                                          Формально это не конфликт, но если хотите — в определении графа используйте вместо i, допустим u. И не забудьте, что ребра есть для всех составных u.

                                          Но я перключился с теории на эксперимент. По первому впечатлению, как уже сообщил ранее, моя реализация работает согласно теоретической оценки. Но прежде, чем перейти к более детальному обсуждению, хочу напомнить, что авторитетные математики предостерегают о подводных камнях в практическом применении теории вычислительной сложности. М.б. мы имеем дело именно с таким непростым случаем. Т.к. речь идет о графах, ограничусь ссылкой: А.А. Зыков, Основы теории графов, М.: Вузовская книга, 2004, С. 9-10. В нашем более частном случае проблема состоит в следующем: как считать количество операций в цикле с предусловием:
                                           while cond do something;

                                          Нпр., если из n^2 обращений к этому циклу процедура something выполняется не более n раз? — М.б. считать только n вызовов something. Но, операции для расчета формулы условия cond выполняются n^2 раз.
                                          Моя реализация обсуждаемого алгоритма (переделана из Листинг 2 в статье)
                                          procedure calc (start : integer);
                                            var
                                             i,j,p : integer;
                                             doit : boolean;
                                            begin
                                              for i := 2 to n do
                                               begin
                                                if lp [i] =0 then
                                                 begin
                                                   lp [i] := i;
                                                   inc (prCount);
                                                   pr [prCount] := i;
                                                 end;
                                                j:= 0;
                                                repeat
                                                  doit := false;
                                                  inc (j);
                                                  if j<= prCount then
                                                   begin
                                                     p := pr[j];
                                                     doit := (p <= lp [i]) and (p*i<=n);
                                                     inc (stepAll);
                                                     if doit then
                                                      begin
                                                        lp [p*i] := p;
                                                        inc(step);
                                                      end; // if doit
                                                   end // if j<= prCount
                                                until not doit;
                                               end;
                                            end; //calc
                                          


                                          Если смотреть выполнение условий внутреннего цикла, то счетчик step будет меньше n. Действительно по Вашему доказательству — больше n ребер в заданном графе быть не может. Но вот отношение stepAll/n растет следующим образом:
                                          n=1000 stepAll/n=1.819
                                          10000 1.874
                                          100000 1.903
                                          1000000 1.921
                                          10000000 1.933
                                          100000000 1.942,

                                          т.е. с ростом n отношение stepAll/n увеличивается, что внушает сомнение в чисто линейной зависимости. Будет интересно выслушать комментарии, при этом напомню с чего начал — это предварительные впечатления.

                                          Прелесть (кроме ассимтотики) этого алгоритма в том, что помимо простых чисел автоматом получается возможность быстро раскладывать на простые множители все числа до n.
                                          С этим полностью согласен.

                                            0

                                            Счетчик stepAll, очевидно, срабатывает примерно n * (2-1/logn) раз.
                                            Это видно в ваших числах — при росте n в 10 раз, n/(2-stepAll) увеличивается почти на одно и тоже число. Объясняется очень просто: по одному разу оно срабатывает для каждого числа — когда цикл должен закончится (тут doit будет false).
                                            Плюс для каждого ребра в графе, тело цикла выполнится один раз (вместе с проверкой; doit будет — true). Ребер ровно столько, сколько составных чисел — примерно n-n/log n. Вот и получается n + n-n/logn = n*(2-1/log n). Можно с уверенностью сказать, что countAll будет не больше 2n всегда.


                                            Обратите внимание, слово "примерно" выше относится к тому, что нет точной формулы для количества составных чисел до n, а не к моей степени уверености в формуле (она 100%).


                                            Т.к. речь идет о графах ограничусь ссылкой: А.А. Зыков, Основы теории графов, М.: Вузовская книга, 2004, С. 9-10

                                            На самом деле все очень просто. Операция condition для цикла "while condition do something" выполнится ровно столько раз, сколько something, плюс столько раз, сколько цикл будет запущен. В этом алгоритме цикл whilе будет запущен для кажого i=2..n. Никаких n^2 там быть не может.

                                              0
                                              Когда и если на Хабре (или где еще) опубликуете свое доказательство этого алгоритма — будет интересно почитать.
                                                0

                                                Уже опубликовал в комментарии.


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


                                                Кстати, в догонку к вашему комментарию про stepAll: добавьте, пожалуйста, вывод stepAll-step. Оно всегда будет n-1.

                                                  0
                                                  Кстати, в догонку к вашему комментарию про stepAll: добавьте, пожалуйста, вывод stepAll-step.

                                                  вывод stepAll-step
                                                  Sieve of Eratosthenes Line version 1.0.1d2
                                                  N= 1000
                                                  Time is 0 sec.
                                                  Found 168 primes.
                                                  stepAll 1819, step 831, stepAll-step=n-1 FALSE
                                                  — Sieve of Eratosthenes Line version 1.0.1d2
                                                  N= 10000
                                                  Time is 0 sec.
                                                  Found 1229 primes.
                                                  stepAll 18744, step 8770, stepAll-step=n-1 FALSE
                                                  — Sieve of Eratosthenes Line version 1.0.1d2
                                                  N= 100000
                                                  Time is 0 sec.
                                                  Found 9592 primes.
                                                  stepAll 190341, step 90407, stepAll-step=n-1 FALSE
                                                  — Sieve of Eratosthenes Line version 1.0.1d2
                                                  N= 1000000
                                                  Time is 0.0160002149641514 sec.
                                                  Found 78498 primes.
                                                  stepAll 1921332, step 921501, stepAll-step=n-1 FALSE
                                                  — Sieve of Eratosthenes Line version 1.0.1d2
                                                  N= 10000000
                                                  Time is 0.124999950639904 sec.
                                                  Found 664579 primes.
                                                  stepAll 19334973, step 9335420, stepAll-step=n-1 FALSE
                                                  — Sieve of Eratosthenes Line version 1.0.1d2
                                                  N= 100000000
                                                  Time is 1.203000289388 sec.
                                                  Found 5761455 primes.
                                                  stepAll 194237314, step 94238544, stepAll-step=n-1 FALSE

                                                  Оно всегда будет n-1

                                                  К сожалению, нет.
                                                  что еще там не понятно?

                                                  В вики не указаны размеры массивов — я сделал просто:
                                                  var pr :   array [1..N] of integer;
                                                   lp :   array [2..N] of integer;

                                                  Но можно экономнее.
                                                    0

                                                    Не могли бы вы перенести "inc(stepAll)" прямо перед "if j<= prCount"?


                                                    Тогда разность должна быть n-1.


                                                    Ведь по той же логике, как и с while, в "if condition then something", если something выполнится ограниченное количество раз, но if вызывать слишком много раз, сложность может быть больше. Поэтому логично увеличивать счетчик операций за if.

                                                      0
                                                      логично увеличивать счетчик операций за if.
                                                      Действительно логично.
                                                      Работает:
                                                      
                                                      procedure calc (start : integer);
                                                        var
                                                         i,j,p : integer;
                                                         doit : boolean;
                                                        begin
                                                          for i := 2 to n do
                                                           begin
                                                            if lp [i] =0 then
                                                             begin
                                                               lp [i] := i;
                                                               inc (prCount);
                                                               pr [prCount] := i;
                                                             end;
                                                            j:= 0;
                                                            repeat
                                                              doit := false;
                                                              inc (j);
                                                              inc (stepAll);    // new place ------!!!!!! 
                                                              if j<= prCount then
                                                               begin
                                                                 p := pr[j];
                                                                 doit := (p <= lp [i]) and (p*i<=n);
                                                      //           inc (stepAll);
                                                                 if doit then
                                                                  begin
                                                                    lp [p*i] := p;
                                                                    inc(step);
                                                                  end; // if doit
                                                               end // if j<= prCount
                                                            until not doit;
                                                           end;
                                                        end; //calc
                                                      


                                                      — Sieve of Eratosthenes Line version 1.0.1d3
                                                      N= 1000
                                                      Time is 0 sec.
                                                      Found 168 primes.
                                                      stepAll 1830, step 831, stepAll-step=n-1 TRUE
                                                      — Sieve of Eratosthenes Line version 1.0.1d3
                                                      N= 10000
                                                      Time is 0 sec.
                                                      Found 1229 primes.
                                                      stepAll 18769, step 8770, stepAll-step=n-1 TRUE
                                                      — Sieve of Eratosthenes Line version 1.0.1d3
                                                      N= 100000
                                                      Time is 0 sec.
                                                      Found 9592 primes.
                                                      stepAll 190406, step 90407, stepAll-step=n-1 TRUE
                                                      — Sieve of Eratosthenes Line version 1.0.1d3
                                                      N= 1000000
                                                      Time is 0 sec.
                                                      Found 78498 primes.
                                                      stepAll 1921500, step 921501, stepAll-step=n-1 TRUE
                                                      — Sieve of Eratosthenes Line version 1.0.1d3
                                                      N= 10000000
                                                      Time is 0.108999735675752 sec.
                                                      Found 664579 primes.
                                                      stepAll 19335419, step 9335420, stepAll-step=n-1 TRUE
                                                      — Sieve of Eratosthenes Line version 1.0.1d3
                                                      N= 100000000
                                                      Time is 1.21899987570941 sec.
                                                      Found 5761455 primes.
                                                      stepAll 194238543, step 94238544, stepAll-step=n-1 TRUE
                                0
                                MarazmDed «Решето Эратосфена» — это, если я правильно помню, алгоритм, который выщитывает простые числа в диапазоне от 2 до N путём вычёркивания в этом диапазоне всех чисел, больше текущего простого числа, которые делятся на это число. Мы начинаем с 2. Следующим простым числом будет первое невычеркнутое число. Так что, сам алгоритм предписывает сохранять информацию о том, «вычеркнуто» данное число или нет, для чисел в диапазоне 2,…, N.

                                Бесспорно, информацию можно хранить по-разному. Например, сделав утверждение, что поскольку все чётные числа непростые, мы всегда расматриваем только нечётные. Таким образом массив уменьшается в два раза…

                                Вы, судя по всему, предлагаете хранить только простые числа в двоичном дереве. А как же непростые? Как алгоритм будет «вычёркивать» соответствующие числа больше текущего? Или Вы, всё-же, предлагаете хранить информацию о том, вычеркнуто число или нет, для чисел от 2 до N в двоичном дереве? Тогда это скорее не оптимизация, а совсем даже наоборот…
                                  0
                                  «Решето Эратосфена» — это, если я правильно помню, алгоритм, который выщитывает простые числа в диапазоне от 2 до N путём вычёркивания в этом диапазоне всех чисел, больше текущего простого числа, которые делятся на это число. Мы начинаем с 2. Следующим простым числом будет первое невычеркнутое число.

                                  Да, прошу прощения — меня заглючило.
                                  Но как бы там ни было, выделение гигабайта памяти — это сильно. А если терабайт потребуется? Тоже так написать? Просто нужно смотреть на применимость алгоритмов. Для больших N — не использовать решето Эратосфена, или бить диапазоны на куски.
                                0
                                Первая пришедшая в голову идея. Записываем, нпр., в дерево числа до 1 млн. начинаем удалять четные, удаляя каждую вершину дерева. Дерево уменьшилось вдвое, добавляем к дереву второй лимон чисел, продолжаем удалять четные. И т.д., пока дерво не достигнет лимита памяти. Запоминаем, то число, на котором встали с удалением кратных 2двум, обозначим его х2, Переходим к удалению троек (т.е. что делится на 3) в дереве нечетных чисел. Доходим до х2. Останавливаем удаление троек и запоминаем х3 = х2. Добавляем в дерево следующую порцию чисел, удаляем двойки, потом с х3 удаляем тройки. Аналогично с другими числами.
                                  0
                                  Первая пришедшая в голову идея. Записываем, нпр., в дерево числа до 1 млн. начинаем удалять

                                  Да у вас вообще не должно быть в дереве лишних элементов!
                                  Изначально — дерево пустое. И функция проверки на простоту для любого числа будет возвращать false.
                                  Затем запускаете алгоритм Эратосфена. Нашли число — добавили его в дерево. Четные числа вообще не надо проверять. Просто в цикле шаг меняете и все.
                                    0
                                    Затем запускаете алгоритм Эратосфена. Нашли число — добавили его в дерево.

                                    вот это вот — ну бред же.
                                    что конкретно значит у вас «нашли число»? как нашли?
                                      0
                                      2n+1, где n — шаг цикла?
                                      Хотя да, как хранить инфу, что вычеркиваем…
                                        0
                                        т.е. все не простые числа будут в итоге в дереве — так?
                                        ну и почему вы думаете, что это займёт меньше памяти? число, пара ссылок — на 64-бит системе — это в (1+8+8) 17 раз больше, чем один байт в массиве.

                                        Далее, для дерева надо по нему пробежаться (случайный доступ к памяти в среднем на пол-глубины), в каких то случаях перебалансировать, в других — аллоцировать память для нового узла.
                                        Сравниваем с массивом — индексация (одно умножение) и один доступ в память на запись. Ну или если указатель — одно сложение + доступ.

                                        в чем преимущество дерева?
                                          0
                                          А вообще, если говорить про вычеркивание — вычеркивают же только кратные простым, кстати. То есть дерево простых чисел уже содержит инфу для дальнейшего вычисления, то есть кратность нужно проверять лишь с уже найденными простыми.
                                          а вот как сегментировать весь массив, если для вычеркивания мы должны каждый раз перебрать его весь с заданным шагом n?
                                          ну, чтоб не работать с терабайтом чисел.
                                            0
                                            и да, чем лучше — без понятия. просто вопрос был как найти)
                                              0
                                              хотя есть мысль, если создать массив на n элементов и его итеративно изменять k раз, после чего по каждому уже найденному простому вычеркнуть, каждый раз сохраняя невычеркнутое в итоге в список простых.
                                              память будет жрать удвоенный массив простых чисел и наперёд известный по размеру массив для вычислений…
                                              ушел спать, ибо брежу уже…
                                              ps. я не программист, я так, учился очень давно и так, балуюсь иногда
                                            0
                                            что конкретно значит у вас «нашли число»? как нашли?


                                            Согласно «следствию» из «алгоритма Эратосфена» получается, что любое НЕпростое число можно представить в виде произведения ПРОСТЫХ чисел.

                                            т.е. чтобы определить, является ли число НЕпростым, достаточно проверить его делимость на несколько первых ПРОСТЫХ чисел в последовательности.

                                            Причем произведение максимального простого числа на минимальное(число 2) должно быть не больше чем проверяемое число. (Как обосновать данное утверждение еще не придумал, но вроде так получается-)

                                            Следовательно, расход памяти:
                                            1.Размер текущего проверяемого числа
                                            2.Структура для хранения найденных ПРОСТЫХ чисел.
                                            3.«память» для проверки делимости очередного числа.

                                            Что-то мне подсказывает, данный алгоритм можно оптимизировать по производительности. Исключение четных чисел — частный случай такой оптимизации.
                                            Так же можно исключить числа кратные 3,5,7 и т.п. т.е. кратные найденным простым числам.
                                              +1
                                              чтобы определить, является ли число НЕпростым, достаточно проверить его делимость на несколько первых ПРОСТЫХ чисел в последовательности.
                                              Не только первых. Пусть на каком-то шаге имеем максимальное для данного шага простое число М. Конструируем из него непростое число, не содержащее меньших делителей — это будет М в квадрате.
                                                0
                                                Что-то мне подсказывает, данный алгоритм можно оптимизировать по производительности.

                                                Этот алгоритм жрет меньше памяти, да (в log n раз меньше). Но работает за n^2/log^2 n. Для 10^9 вы его уже не дождетесь.
                                                Это именно то самое "неправильное" решето реализованное на ФП в оригинальном топике.


                                                Откуда такая оценка? Вам каждое простое число в любом случае придется проверить на делимость всеми предыдущими простыми. Всего простых n/log n. Значит проверок будет ассимптотически квадрат этого числа.


                                                При оптимизации и проверке только на делимость простых меньше корня текущего, у вас будет оценка n sqrt(n) / log^n. Уже лучше, но все-равно сильно медленее.


                                                А проблемы с потреблением памяти решета решаются очень просто — нужно хранить только кусок большого массива в памяти. При этом придется хранить в памяти все простые до корня из n и вычеркивать их из каждого куска массива отдельно. Так и n=10^12 можно просеять с несколькими мегабайтами памяти.

                                                  0
                                                  А проблемы с потреблением памяти решета решаются очень просто — нужно хранить только кусок большого массива в памяти.
                                                  и при этом массив может быть чисто битовый, когда номер элемента и связан с значением числа, а бит просто указывает — вычеркнут элемент или нет.
                                                  При этом придется хранить в памяти все простые до корня из n и вычеркивать их из каждого куска массива отдельно. Так и n=10^12 можно просеять с несколькими мегабайтами памяти.
                                                  И для каждого корня каждый раз рассчитывать с какого числа продолжить вычеркивание для нового куска массива. А в чем оптимальнее хранить простые числа? Линейный список?
                                                    0
                                                    И для каждого корня каждый раз рассчитывать с какого числа продолжить вычеркивание для нового куска массива. А в чем оптимальнее хранить простые числа? Линейный список?

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


                                                    Лучше всего хранить эти маленькие простые в массиве для локальности. Его можно сразу выделить на sqrt(n) / log(n) * 3. Этого должно хватить для больших n.

                                                      0
                                                      Можно еще удвоить потребление памяти но ускорить работу, если хранить для каждого простого следующее число на вычеркивание.
                                                      Ну это вчера я перед сном тоже думал:
                                                      память будет жрать удвоенный массив простых чисел и наперёд известный по размеру массив для вычислений…

                                                      эти маленькие простые
                                                      под конец для границы в миллиард — не такие уж и маленькие… unsigned long int минимум, то есть по 4 байта, и второе не меньше. Если выше миллиардов считать, то уже unsigned long long int каждое…
                                                    0
                                                    При оптимизации и проверке только на делимость простых меньше корня текущего, у вас будет оценка n sqrt(n) / log^n.


                                                    нет, проверять «квадратом» максимальное простое число для текущего проверяемого — перебор.

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

                                                    вот в общем-то алгоритм (typescript):

                                                        // Массив для простых чисел
                                                        const primes = [2];
                                                        // Максимальное значение диапазона поиска простых чисел
                                                        const limit = 1000000;
                                                    
                                                    
                                                        // Первое проверяемое число
                                                        let next = 3;
                                                    
                                                        console.time('primes');
                                                        while (next < limit) {
                                                    
                                                          // Простое число пока не найдено
                                                          let find = false;
                                                    
                                                          /*
                                                     every выполняет переданный в аргументах колбек для каждого элемента массива primes, пока колбэк возвращает - true
                                                    */
                                                          primes.every((num: number) => {
                                                    
                                                     /* 
                                                    Если next делится на num без остатка, прерываем every, т.к. next - не простое число
                                                    */
                                                            if (next % num === 0) {
                                                              return false;
                                                            }
                                                    
                                                      /*
                                                     Если every еще не прерван, а мы уже дошли до num, произведение которого на   "минимальное" простое число больше текущего проверяемого то проверку можно заканчивать, next - точно простое число
                                                    */
                                                            if (next < (2 * num)) {
                                                              find = true;
                                                              return false;
                                                            }
                                                            return true;
                                                          });
                                                    
                                                    
                                                          if (find) {
                                                            primes.push(next);
                                                          }
                                                          next++;
                                                        }
                                                    
                                                        console.log('count', primes.length);
                                                        console.timeEnd('primes');
                                                    
                                                0
                                                Смотрю делимость на 3 нечетных чисел. В дерево попадает 25. Но это не простое число делится на 5. И часто нужна балансировка, т.к. числа будут добавляться в возрастающем порядке, и дерево будет вырождаться в линейный список с максимальным временем поиска. М.б. сохранять несколько чисел в буфере, а потом добавлять в дерево случайнным образом?
                                                  0
                                                  Смотрю делимость на 3 нечетных чисел. В дерево попадает 25.

                                                  Про дерево я сморозил глупость. Это тоже напоминание о том, что сперва нужно подумать, а потом — писать :)
                                                  Проблема в том, что у любого алгоритма есть свои ограничения.
                                                  И если в исходных текстах массив на миллиард элементов — выглядит вполне безобидно, то в скомпилированной программе — это будет сильно. Если вы приводите примеры с такими размерностями, то не мешает задуматься о структурах данных. Например, делить целиковый диапазон на поддиапазоны. Или поискать более экономный по памяти алгоритм.
                                                    0
                                                    Не понял: 1 гиг — это много для среднего современного ПК? В достаточно крупной задаче есть чего мерять, а при N=200 измерять будет проблематично ;)
                                                      0
                                                      Не понял: 1 гиг — это много для среднего современного ПК?

                                                      А у вас в программе одна единственная структура данных? :) Программа работает в изолированной среде? Ну и потом, а что если ваши аппетиты вырастут и будет не миллиард, а триллион. Аккуратнее надо с числами. Понятно, что пример — учебный. Но в этом и есть проблема. Студенты учатся на учебных примерах и о таких вопросах начинают задумываться не в ВУЗе, а на реальной работе, после десятка-другого неудачных экспериментов. В вашем случае, какие-никакие проверки на память просятся.

                                                      1гиг — это еще сильно зависит от реализации. Если бы вы тоже самое писали на c++, то это было бы 4гига. А это уже фатально :)
                                                      Битовые маски — это как раз то решение, которое вам имеет смысл использовать. Для дельфи в 8 раз память с экономите. Для плюсов — в 32 раза.

                                                      В достаточно крупной задаче есть чего мерять

                                                      Это вы уже применение к задаче находите. Но задача формулируется не как «нагрузочное тестирование, на примере решета эратосфена», а именно как поиск простых чисел.
                                                        0
                                                        1гиг — это еще сильно зависит от реализации. Если бы вы тоже самое писали на c++, то это было бы 4гига. А это уже фатально :)


                                                        Нет. sizeof bool = 1 в сях и плюсах. 1 байт. можно ужать в бит, но пострадает скорость доступа к этому счастью.

                                                        4гига. А это уже фатально

                                                        опять же — нет. типичный комп сейчас имеет 8GB рамы. у программеров 16-32 и более.
                                                        мой пример — дома — ноуты 3шт. все по 8ГБ, стационарник — 16. на работе 32гига. не потому, что прям вот всё задействовано, а потому, что меньше не ставят уже.
                                                          0
                                                          Нет. sizeof bool = 1 в сях и плюсах. 1 байт.

                                                          Не байт, а char. :) sizeof возвращает размер не в байтах, а в char'ах. А размер char'а не обязан быть 1 байт. Т.е. bool в плюсах у вас может спокойно занимать 4 байта.

                                                          1 байт. можно ужать в бит, но пострадает скорость доступа к этому счастью.

                                                          Если постараться, то скорость пострадает у вас не сильно.

                                                          опять же — нет. типичный комп сейчас имеет 8GB рамы. у программеров 16-32 и более.

                                                          Если у вас на компе 8Gb, и вы отдаете тут же половину непонятно куда, то отзывчивость вашей системы пострадает ой как сильно. Если у вас x32 (что, слава богу, уже редкость), то вы получите прямой выкидыш по памяти. И это еще вопрос, в x64 вы компилируетесь или в x32. Т.е. даже на 64битной системе можете получить выкидыш.
                                                            0
                                                            Т.е. bool в плюсах у вас может спокойно занимать 4 байта.

                                                            честно говоря, кроме редких DSP не встречал процов с char более байта. но вы правы, может такое быть.

                                                            На интел 32-бит — мертво. 64-бит помимо памяти дают ещё дофига регистров, и это видно в тяжелых задачах даже на глаз. так что сейчас компилять в 32-бит — смысла никакого. только для легаси и/или 100 лет поддержки. За последние 5 лет у меня только один проект был 32-бит — и то для XP — пром.оборудование, другую ос не поставить.
                                                            и вы отдаете тут же половину непонятно куда, то отзывчивость вашей системы пострадает ой как сильно.

                                                            не, вы мыслите в категориях разумной достаточности. т.е. если есть 8 гиг то это было сделано для дела, память на 80% используется и 4 отожрать — тормоза. Сейчас не так. У меня из 8 гигов 5 свободны (2 кеш пользует, 3 совсем свободны). выделить 4 — я не замечу. И именно поэтому ставят много памяти — что бы не встало колом, когда кто то жирный в память залезет. ну и дешевая она. была бы дорогая — сидели бы на гиге и хромом не пользовались. мои первые 16мегов я за $600 купил… эх времена были… зато Windows 95 летала :-)
                                                          0
                                                          Понятно, что пример — учебный.
                                                          В статье не указано образовательных хабов.
                                                          Ну и потом, а что если ваши аппетиты вырастут
                                                          Буду, нпр., искать грант на покупку/аренду нужного железа ;)
                                                          Много лет назад участвовал в международном конкурсе Интел (не для студеньов, а дл профи). Все задачи были на грани возможностей тогдашнего железа.
                                                          Но задача формулируется не как «нагрузочное тестирование, на примере решета эратосфена», а именно как поиск простых чисел.
                                                          Но цель поиска в формулировке отсутствует.
                                                            0
                                                            Буду, нпр., искать грант на покупку/аренду нужного железа ;)

                                                            Первое, с чего вы начнете, это попытаться оптимизировать алгоритм и выжать максимум из железа, как я понимаю :)
                                                              0
                                                              Не факт. Все зависит от конкретной задачи.
                                                      0
                                                      а тут и хватит линейного списка в две переменных, массив промежуточный ограниченный на число и флаг вычеркнут или нет и всё это в несколько итераций…
                                                      0
                                                      алгоритм эратосфена и «находит» число по его текущему состоянию в массиве, а т.к. в дереве его нет, то будет считаться, что оно не простое, по-этому дерево можно строить только реверсивное, и хранить там НЕ простые числа, но тогда и выигрыш по памяти будет отсутствовать (на самом деле будет использоваться даже больше памяти).
                                                      И еще довольно интересно, как по сравнению с эратосфеном будет работать простая проверка всех чисел каким-нибудь быстрым вероятностным тестом простоты (причем с учетом того, что числа небольшие, тест может быть упрощен по вычислительной сложности).
                                                      Ну, интересно не настолько, чтобы самому писать BPSW, а настолько, что если бы кто-то это сделал, то почитать
                                                  0
                                                  Вопрос в том, что чем больше числа, тем реже будут попадаться простые, соответственно перестройка дерева

                                                  Кстати, плотность простых чисел падает относительно медленно. Количество простых чисел до n приблизительно равно n / ln n для больших n.

                                                    0
                                                    Перестройка тоже разная бывает. Если задействовано 3 элемента — то ерунда. Ну вставка записей даже в огромную БД не скажу, что прям лагает. Т.е. решаемо.
                                                    0
                                                    Вы в дерево можете добавлять элементы динамически. Да, балансировка дерева — это затраты времени. Вопрос в том, что чем больше числа, тем реже будут попадаться простые, соответственно перестройка дерева — относительно редкая операция.

                                                    Если мы начнём искать простые с начала числового ряда — дерево потребуется перебалансировать довольно часто, т.к. каждое следующее число будет больше предыдущего.
                                                    Но если искать простые с двух сторон поочерёдно:
                                                    1, N, 2, N-1, 3, N-2 и т.д.
                                                    дерево будет собираться более-менее равномерно, и возможно, количество перебалансировок дерева будет минимальным.
                                                    Мне так кажется…
                                                      +1
                                                      Да, это все хорошо. Проблема в другом :) Меня — заглючило. Решето Эратосфена — про массивы, а не про деревья. Сам алгоритм предполагает, что есть массив. И процесс поиска — это вычеркивание пометок. Эратосфен, думаю, не предполагал, что людям придется вычислять триллион первых простых чисел :), поэтому алгоритм занимает O(n) памяти.

                                                      Другое дело, что конструкция array [2..1000000000] of boolean — далеко не самый удачный вариант. А решить можно по разному:
                                                      1) разбить лярд на диапазоны сильно скромнее
                                                      2) Использовать более сложные структуры данных, например std::vector (TArray)
                                                      3) использовать битовые маски.
                                                      4) не использовать решето Эратосфена для больших размерностей.
                                                        0
                                                        Думаю, что для алгоритма «Решета» не требуется исходный массив с числовым рядом от 1 до N, достаточно крутить цикл от 1 до N, проверяя каждое i на «Эратосфенность», и складывая истинные результаты в массив, дерево или список.
                                                        Нам ведь не требуется после проверки очередного числа возвращаться к ранее проверенным элементам ряда для их «перепроверки». По этому исходный массив — пустая трата памяти.
                                                          0
                                                          Думаю, что для алгоритма «Решета» не требуется исходный массив с числовым рядом от 1 до N, достаточно крутить цикл от 1 до N, проверяя каждое i на «Эратосфенность»

                                                          Меня тоже поначалу на этом заглючило. Нет, число не проверяется на эратосфенность. Просто для каждого простого числа вычеркиваются все числа, кратные ему. Сходу не могу придумать подходящую структуру данных, чтобы алгоритм не кушал память. Единственный вменяемый вариант — битовые маски, которые сокращают потребление памяти в 8 раз.
                                                            0
                                                            Единственный вменяемый вариант — битовые маски, которые сокращают потребление памяти в 8 раз.

                                                            Еще можно сегментировать массив. Если хранить дополнительно все простые числа до sqrt(n) — то можно вычеркивать числа из массива отдельно в каждом куске размера sqrt(n) и хранить в памяти только текущее "окно".

                                                            0
                                                            достаточно крутить цикл от 1 до N, проверяя каждое i на «Эратосфенность», и складывая истинные результаты в массив, дерево или список
                                                            Нужно помнить вычеркнутые числа. Иначе вычеркнули кратные 7 в одном цикле, далее опять их же будем проверять на кратность 11, где они не все вычеркнуться? Такое работать не будет.
                                                  0
                                                  www.spoj.com/problems/PRIMES2 — как раз задачка на поиск простых до миллиарда. Самое быстрое решение просеивает за 0.21 секунды на Intel Xeon E3-1220 v5. Алгоритм — segmented sieve of Eratosthenes with wheel factorization modulo 210
                                                    0
                                                    А где решение?
                                                    –1
                                                    del
                                                      0
                                                      Любые простые числа за исключением 2 и 3 подчиняются простой формуле 6*N ± 1. То есть, любое простое число это какое-то натуральное N умноженное на 6 плюс или минус один. ВСЕ простые числа кроме 2 и 3 обладают этим свойством. Обратное, естественно, неверно. Доказывается элементарно.
                                                      Так вот, эта формула как минимум в 6 раз снижает сложность решета.
                                                        0

                                                        По идее, в три — проверяется только каждое третье число, или я что-то не так понял?

                                                          0

                                                          В 3 раза, (2/1)(3/2) = 3.


                                                          Если брать простые числа, которые взаимно просты с 2, 3, 5, 7 — Wheel factorization, то скорость возрастёт примерно в (2/1)(3/2)(5/4)(7/6) = 210/48 = 4.375 раза. Для миллиарда колесо делать больше невыгодно.

                                                            +1
                                                            Любые простые числа за исключением 2 и 3 подчиняются простой формуле 6*N ± 1.

                                                            Сомнительное утверждение. Можете это доказать? Особенно про «ВСЕ».
                                                              +1
                                                              6N, 6N+2, 6N+4 — чётные, 6N+3 делится на 3, остаётся 6N+1 и 6N+5, разве нет? Никто ж не говорит, по идее, что все такие числа — простые. Только что все простые числа (кроме двух) — обязательно такие.
                                                                0
                                                                Спасибо, уже разобрался. Странно, факт — элегантный и простейший, но, почему-то в вики про это ни слова.
                                                                  0
                                                                  Ещё школьником заметил, что при записи простых чисел в 6-чной системе они будут оканчиваться на 1 или 5 (кроме чисел 2 и 3).
                                                                  0
                                                                  Да, любопытная формула-)
                                                                  Но это формула не вычисления простого числа.
                                                                  В любом случае, ее результат еще надо проверять на «простоту» 2 раза-)
                                                                  Так что прироста в производительности не будет, как минимум ощутимого.

                                                                  например N=6
                                                                  X1 = 6 * 6 + 1 = 37
                                                                  X2 = 6 * 6 — 1 = 35

                                                                  и теперь, чтобы «доказать», что какое-то из этих чисел простое, необходимо попытаться разложить их на множители.-)
                                                                    0
                                                                    Так речь-то не о замене перебора по возрастанию на формулу, а о том, чтобы заранее отсечь заведомо неподходящие случаи.
                                                                      0
                                                                      Решето это сказать, что все кратные, например, 7 элементы массива от 1 до N — вычеркиваем. При этом порядковый номер элемента массива по сути и есть его значение. То есть вы в цикле от 2 до k говорите что элементы 14, 21… 7*k — точно не простые.
                                                                      У вас в массиве же 1/3 элементов и под каким номером то же 49 число — не понятно, придется не обращаться по номеру элемента, а искать по элементам есть ли в массиве число 49?
                                                                0
                                                                Так вот, эта формула как минимум в 6 раз снижает сложность решета.
                                                                Во-первых, таки в 3 (слагаемые 0,2,3,4 убираем, 1 и 5 оставляем, 2 из 6, то есть треть).
                                                                Во-вторых, для именно решета это не особо снижает сложность, ибо там просто вначале вычеркивают всё, кратное 2, потом 3, потом 5, потом 7 и т.д. Таким образом массив сократить можно, но количество проверок по сути не изменится, просто для части проверок кратного, допустим, 7 элементов в массиве просто не будет. Вот только если до этого ты просто говорил, что элемент массива 49 — вычеркиваем, то сейчас тебе нужно найти элемент массива с значением 49 и уже его вычеркнуть.
                                                                Не вижу упрощения…
                                                                +2

                                                                Если число делится на что-то большее, чем корень из него, то, очевидно, оно делится на что-то меньшее. Таким образом, при фиксированном n можно обрабатывать поток окном длины корень из n, что существенно снижает требования по памяти.

                                                                  +2
                                                                  Если число делится на что-то большее, чем корень из него,

                                                                  Как может число делиться нацело на что-то большее корня этого числа? sqrt(N) * sqrt(N)= N

                                                                  то, очевидно, оно делится на что-то меньшее.

                                                                  С чего вдруг?
                                                                    +1

                                                                    Например так, как 100 делится нацело на 50.

                                                                      +2
                                                                      Как может число делиться нацело на что-то большее корня этого числа? sqrt(N) * sqrt(N)= N

                                                                      Если оно составное и не является квадратом простого числа.
                                                                      Как, например, число 26 среди делителей имеет число 13, которое больше чем sqrt(26)=~ 5.1.


                                                                      С чего вдруг?

                                                                      Ситуации, когда N имеет два делителя p_1, p_2, таких что p_1 > sqrt(N), p_2 > sqrt(N), быть не может, поскольку произведение p_1 * p_2 будет заведомо больше N.
                                                                      Значит, если существует делитель p_1 > sqrt(N), то будет существовать делитель p_2 < sqrt(N).

                                                                    0
                                                                    Остается применить решето и уложиться в ограничения
                                                                      0
                                                                      Скорее всего, авторы Википедии сами утонули в море информации по РЭ и пропустили эту работу.

                                                                      Ничего авторы не утонули, просто вы поленились прочитать статью полностью, ну или хотя бы пролистать оглавление. Пролистали бы — обратили бы внимание на решето только по нечетным числам, а заодно более интересное решето за линейное время
                                                                        0
                                                                        И где там последовательность (3)? И почему оптимизированной реализацией назван другой вариант? Приведенная там последовательность (Листинг 1 у меня) избыточна.
                                                                          0
                                                                          который в Википедии преподносится как оптимальный

                                                                          И почему оптимизированной реализацией назван другой вариант?

                                                                          Видите, Вы сами себя поправили: в википедии приведен «оптимизированный» вариант, а не оптимальный. Думаю, что здесь есть «стилистическая» ошибка от авторов статьи в вики, наверно подразумевалась оптимизация базового алгоритма решета Эратосфена, которая просто убирает ненужные действия.
                                                                          И где там последовательность (3)?

                                                                          Я кидал ссылку на параграф, там описание модификации, но кода нет. В общем то, вы и сами согласились, что модификация не очень хитрая, возможно авторы статьи в вики просто не стали заморачиваться с лишним кодом. Я бы даже предположил, что вот эта страница — оригинал статьи в вики. Если нужен код для проверки решета с линейным временем работы, то его можно взять здесь, советую в нем разобраться.
                                                                          Обладая более чем скудными знаниями по ФП, не берусь судить об ответах, но другие участники обсуждения забраковали некоторые из предложенных сходу решений, указав, что вместо теоретической сложности

                                                                          Я не участвовал в этом обсуждении, но кажется, что асимптотика n^2/log(n) относится не к решету Эратосфена, а к алгоритму, предложенному в этом комментарии, дело в том, что если вы просто напишете цикл типа: for i:=1 to n do «перебрать все простые делители от 2 до i-1 и проверить делится ли i хотя бы на один из них», то получите ровно такую ассимптотику, так как количество простых чисел от 2 до i — это примерно i / log(i). А проблема заключалась ровно в том, что ФП не очень хорошо подходит для реализации РЭ, как и для многих других нетривиальных алгоритмов.
                                                                            0
                                                                            А проблема заключалась ровно в том, что ФП не очень хорошо подходит для реализации РЭ, как и для многих других нетривиальных алгоритмов.

                                                                            В том обсуждении был сделан аналогичный вывод. Т.о. РЭ помогло выявить важную проблему технологии программирования (ФП):
                                                                            Для многих задач в этой парадигме можно сделать очень простой и понятный код. Для других задач чистое ФП все-таки не так хорошо подходит.

                                                                            Я кидал ссылку на параграф, там описание модификации, но кода нет.
                                                                            Про какой параграф речь? Если про РЭ с «линейным» временем — там псевдокод:
                                                                            Вход: натуральное число n

                                                                            Пусть pr - целочисленный массив, поначалу пустой;
                                                                                  lp - целочисленный массив, индексируемый от 2 до n, заполненный нулями
                                                                            
                                                                             для i := 2, 3, 4, ..., до n: 
                                                                               если lp[i] = 0:
                                                                                   lp[i] := i
                                                                                   pr[] += {i}
                                                                               для p из pr пока p ≤ lp[i] и p*i ≤ n:
                                                                                   lp[p*i] := p
                                                                            
                                                                            Выход: все числа в массиве pr.

                                                                            советую в нем разобраться.
                                                                            Код (см. Реализация) почти аналогичен псевдокоду в вики. И как, скажите, пожалуйста, два вложенных друг в друга цикла (первый от 2 до n) могут дать линейное время?
                                                                            Думаю, что здесь есть «стилистическая» ошибка от авторов статьи в вики,
                                                                            И я так думаю. О чем и сказал в статье.
                                                                              0
                                                                              PS BTW Пожалуйста, подскажите, кто знает: как на Хабре оформлять псевдокод? Установил «source lang=code» пропали отступы, установил «delphi» фигурные скобки стали комментами.
                                                                                +1
                                                                                И как, скажите, пожалуйста, два вложенных друг в друга цикла (первый от 2 до n) могут дать линейное время?

                                                                                Внутренний цикл суммарно выполнится O(n) раз. Там так хитро подогнанно, что каждый элемент массива lp[] будет записан ровно один раз. А это единственная операция во вложенном цикле.


                                                                                Почему так происходит понрять чуть сложнее. lp[] — минимальный простой делитель для каждого числа. Все позиции будут подсчитанны: Вот есть число k и его минимальный делитель lp[k]. В момент, когда i в коде будет k / lp[k] внутренний цикл точно дойдет до k, ведь в k/lp[k] не может быть делителей меньше lp[к], иначе бы это был меньший делитель в k. Теперь, почему оно будет подсчитанно только один раз: Когда мы пишем в ичейку lp[k] значение p — i однозначно равно k/p, других вариантов нет. Вот и получается, что внутренняя операция выполниться ровно n раз.

                                                                                  0
                                                                                  Спасибо. Я примерно представил, что Вы хотите сказать, но, к сожалению, то что Вам удалось сказать звучит как-то слишком расплывчато (с учетом того, что сказано в упомянутых источниках). М.б., если поднять первоисточник, то там всё это показано достаточно строго. Можно предположить, что авторы вторичных источников разобрались в первичном, но при пересказе опустили важные моменты, сделав вид, что эти моменты очевидные. Такое, к сожалению, случается с нетривиальными алгоритмами. В результате четкое наглядное доказательство превращается в запутанный ребус. Однако читатель не должен разгадывать ребусы. В мат.журналах существует строгое правило: чтение производится до первой ошибки или неясности. При этом, конечно, встречаются и очень покладистые читатели, которые готовы верить каждому «печатному слову» — им только кажется, что они всё поняли.

                                                                                  Прежде всего возникает вопрос: а зачем тогда внутренний цикл?
                                                                                  внутренний цикл точно дойдет до k
                                                                                  Сколько шагов он будет доходить? Не будет ли он работать вхолостую подбирая нужное значение? Не зависит ли это от реализации?
                                                                                    0
                                                                                    Прежде всего возникает вопрос: а зачем тогда внутренний цикл?

                                                                                    Что бы посчитать для всех k=p*i.


                                                                                    Представьте вычисление этих lp[] в виде графа. Есть n точек в ряд. Проведите ребра из каждой точки k в k/lp[k]. Всего ребер n. Этот алгоритм линейного решета обходит ребра задом-на-перед. Внешний цикл перебирает все вершины. Внутренний перебирает все ребра, втыкающиеся в эту вершину и записывает значение для другого конца ребра. Для каких-то вершин будет много ребер, для каких-то мало, для каких-то не одного. Суммарно — n.


                                                                                    Сколько шагов он будет доходить?

                                                                                    А какая разница? Каждый шаг — одно подсчитанное значение. Каждое значение считается ровно один раз. Всего значений n.

                                                                                      0
                                                                                      Внешний цикл перебирает все вершины. Внутренний перебирает все ребра
                                                                                      Пусть в графе m вершин и n ребер. Граф задан матрицей смежности
                                                                                      g : array [1..m,1..m] of  boolean; 

                                                                                      где g[i,j] = true, если существует ребро (i,j), false — в противном случае. Поставим простейшую задачу: перебором пар вершин удалить все ребра.
                                                                                      Решение:
                                                                                      for i:=1 to m do
                                                                                       for j:=1 to m do
                                                                                        g[i,j] := false;
                                                                                      

                                                                                      Сложность O(m^2), от n не зависит.
                                                                                      Если мы хотим реагировать только на существующие ребра, то можем написать:
                                                                                      for i:=1 to m do
                                                                                       for j:=1 to m do
                                                                                        if g[i,j] then
                                                                                         g[i,j] := false;
                                                                                      

                                                                                      Сложность не изменится, хотя оператор g[i,j] := false; будет выполняться ровно m раз в случае несимметрической матрицы и 2m раз в случае симметрической.

                                                                                      В псевдокоде действителбную сложность можно попытаться замаскировать:
                                                                                      для  i от 1 до m
                                                                                       для  j: (i,j) существует,  j<=m
                                                                                         g[i,j] := false;
                                                                                      

                                                                                      Можно работать только с половиной матрицы выше (или ниже) главной диагонали, но это для наших рассуждений не принципиально.
                                                                                        0

                                                                                        Но тут граф задан списком смежности!

                                                                                          0
                                                                                          Дла списка необходим только один цикл:
                                                                                          для  i  от 1 до n
                                                                                            {
                                                                                             взять_из _списка_ребро (i);
                                                                                             удалить (i);
                                                                                            }
                                                                                          

                                                                                          Сложность O(n).
                                                                                            0

                                                                                            Эм… Список смежности


                                                                                            Для каждой вершины хранится отдельный список всех, смежных с ней. Обход ребер для одной вершины — внутренний список. Обход для всех ребер — перебор вершины — внешний цикл.

                                                                                              0
                                                                                              Пока Гвидо ван Россум делал Питон списком смежности называли и такое, нпр., представление полного графа из 3 вершин: 1-2, 2-3, 3-1.
                                                                                              Нпр., и после Питона я написал:
                                                                                              Такой подход соответствует одному из наиболее экономных представлений графа в виде списка смежности. В частности, он очень удобен для ручного ввода графов. Можно использовать следующий формат для записи ребра:

                                                                                              v-u

                                                                                              где v,u – инцидентные ребру вершины.
                                                                                              Возражений не последовало )
                                                                                              Обход ребер для одной вершины — внутренний список. Обход для всех ребер — перебор вершины — внешний цикл.
                                                                                              Число всех вершин — m, число ребер — n. Допустим наиболее экономную по времени ситуацию, когда в списках нет повтора ребер, как в приведенном примере: 1-2, 2-3, 3-1 — первое число вершина, для которой список, вторая список (в примере они из одного элемента). Обработка всех списков по внутреннему циклу даст kn операций, но внешний цикл перебора вершин — это еще pm операций, где k,p константы, зависящие от реализациии. Т.о. получим O(kn+pm). Однако пока не очевидно, что обсуждаемый алгоритм эквивалентен алгоритму со списком смежности графа.
                                                                                                0
                                                                                                Однако пока не очевидно, что обсуждаемый алгоритм эквивалентен алгоритму со списком смежности графа.

                                                                                                Внешний цикл по i -это фактически перебор вершины.
                                                                                                Внутренний цикл по p — это беребор всех ребер в списке смежности для этой вершины. Там n вершин. Осталось понять, что ребер ровно n. В итоге, как вы указали, весь алгоритм займет O(c1*n+c2*n) = O(n)


                                                                                                Ребра тут — это i->p*i: p <= lp[i].
                                                                                                Главное убедится, что все правые части не равны между собой.
                                                                                                Допустим для двух разных i,j правые концы ребер совпали: i < j, p1*i = p2*j, p1 <= lp[i], p2 <= lp[j].
                                                                                                Поскольку p1 и p2 — простые, то i=p2*k, j=p1*k. Еще, очевидно, что p1 > p2 (ведь при умножении на i<j p1 дает такой же результат). Теперь посмотрим повнимательнее на условия p1 <= lp[i]. Можно подставить i внутрь и раскрыть определение lp (lp — минимальный простой делитель, значит lp[pk] = min(p, lp[k])):
                                                                                                p1 <= lp[p1*k], значит p1 <= lp[k] и p1 <= p2. Но p1 > p2! Вот и противоречие.

                                                                                                  0
                                                                                                  Внутренний цикл по p — это беребор всех ребер в списке смежности для этой вершины. Там n вершин.
                                                                                                  Не понял: в 1 списке смежности (для 1 вершины) n вершин?

                                                                                                  Еще хочу уточнить, что означают "->" и "<= "? Второе означает не больше, т.е. меньше или равно?

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

                                                                                                  (n^2-n)/2,
                                                                                                  где n — число вершин.
                                                                                                    0
                                                                                                    Не понял: в 1 списке смежности (для 1 вершины) n вершин?

                                                                                                    Не n. А от 0 до, видимо sqrt(n)/log(n) — каждому ребру соответствует простое число до минимального делителя i.


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

                                                                                                    При чем здесь наихудший случай? Граф задан вполне конкретный. Вот вам пример для n=10. Ребра в графе 2->4 3->6, 3->9, 4->8, 5->10. Всего 5 ребер (10-1-4, ибо нет ребер в вершину 1 и 4 простых 2,3,5,7). При больших n будет порядка n(1-1/logn) ребер.


                                                                                                    Тут для вершины 2 в списке смежности 1 вершина. Для 3 — две, для 4 и 5 по одной. Для 6 и далее — пустые списки.

                                                                                                      0
                                                                                                      Не n.

                                                                                                      А от 0 до, видимо sqrt(n)/log(n)

                                                                                                      То n, то не n ;) Извините, но «видимо» в доказательстве воспринимается неуместным. Выше я уже сказал:
                                                                                                      М.б., если поднять первоисточник, то там всё это показано достаточно строго.

                                                                                                      Только что попробовал поднять первоисточник — удалось за одну минуту. Попробуйте и Вы. Статья небольшая, но очень насыщенная. По первому впечатлению там иное, гораздо более сложное доказательство и два иных псевдокода. Многое завязано на представление множеств в машине и на реализацию операций со множествами, в частности, на реализацию next, о которой писали Дал У., Дейкстра Э., Хоор К., Структурное программирование. М.:«Мир», 1975. Но которую Вирт и др. так и не реализовали. Особенно привлекла внимание фраза на последней странице в разделе обсуждение:

                                                                                                      We see here a distinction between complexity of an algorithm and the complexity of its mathematical underpinninпs, two quite different things.


                                                                                                      В общем, есть о чем подумать — давайте думать вместе, похоже, с этим алгоритмом не так просто, как показалось авторам википедии.
                                                                                                        0

                                                                                                        Стоп. Могли бы вы уточнить вашу позицию? Сначала я думал, что вы просто не понимаете, почему этот алгоритм имеет линейную сложность, и пытался объяснить почему. Привел пример (к сожалению, не понятный без достаточного знания теории графов), привел набросок формального доказательства.


                                                                                                        Но ваши авторететные отсылки к первоисточнику и обвинения авторов википедии в некомпетентности зародили у меня сомнения, что у вас есть какие-то веские причины думать, что этот алгоритм не O(n)?


                                                                                                        Да, псевдокод в Вики совсем не похож на код в первоисточнике. Он использует ту же декомпозицию составных чисел из теоремы 2.1 из статьи. Но вычеркивает составные числа немного в другом порядке (сначала по возрастанию p^(k-1)*q, потом по p). За 40 лет с первоначальной статьи и алгоритмы и компьютеры сильно шагнули вперед.


                                                                                                        Только что попробовал поднять первоисточник — удалось за одну минуту. Попробуйте и Вы.

                                                                                                        Мне алгоритм в вики нравится больше. Он сильно проще для понимания, реализации и еще и короче. Кстати, там в статье есть еще и algorithm 2, который имеет вообще 3 вложенных цикла! Но тоже линейный и эквивалентен algorithm 1.


                                                                                                        We see here a distinction between complexity of an algorithm and the complexity of its mathematical underpinninпs, two quite different things.

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

                                                                                                          0
                                                                                                          Могли бы вы уточнить вашу позицию?
                                                                                                          Обычная позиция, как для математики, так и для CS. Человек узнает про нетривиальную теорему и кроме формулировки типа «Теорема: алгоритм Х имеет сложность O(n).» ему требуется доказательство, чтобы согласиться. И это не значит, что он изначально не согласен или обвиняет кого-то в некомпетентности. Совершенно стандартная позиция.
                                                                                                          обвинения авторов википедии в некомпетентности
                                                                                                          Скорее в халтуре. Выше я предположил:
                                                                                                          Можно предположить, что авторы вторичных источников разобрались в первичном, но при пересказе опустили важные моменты, сделав вид, что эти моменты очевидные. Такое, к сожалению, случается с нетривиальными алгоритмами. В результате четкое наглядное доказательство превращается в запутанный ребус.
                                                                                                          Теперь, когда я увидел первоисточник, появилось второе обвинение: в правилах вики записано, что вики не место для оригинальных исследований. Вы признали:
                                                                                                          Да, псевдокод в Вики совсем не похож на код в первоисточнике.
                                                                                                          По упомянутому и совершенно обоснованному правилу вики — должна быть ссылка на авторитетный источник, где строго доказан именно этот псевдокод.
                                                                                                          привел набросок формального доказательства
                                                                                                          Спасибо. К сожалению, наброски не доказательство. Тут принципиальный момент.
                                                                                                          без достаточного знания теории графов
                                                                                                          Я не увидел в Вашем примере недостаточность знаний в области теории графов. Вроде со стороны графов все просто. М.б. единственная сложность: мое замечание про максимальное число ребер графа? Если это не очевидно — могу привести очень простое и короткое доказательство.
                                                                                                            0
                                                                                                            Скорее в халтуре. Выше я предположил:

                                                                                                            Да, ссылки на доказательство в вики просто нет.


                                                                                                            Вот доказательство:


                                                                                                            Рассмотрим алгоритм.


                                                                                                            Введем граф из n-1 вершин, пронумерованных от 2 до n.
                                                                                                            Для всех составных i проведем ребро из i/lp(i) в i. Напоминаю, lp(i) — минимальный простой делитель числа i.


                                                                                                            Утверждение 1: в этом графе ровно столько ребер, сколько составных чисел в отрезке 2..n.


                                                                                                            Очевидно — каждое ребро заканчивается в составном числе и однозначно задается концом по определению.


                                                                                                            Утверждение 2: Из вершины i выходят ребра в вершины j = p*i, т.ч. p — простое и p<= lp(i).


                                                                                                            Доказательство

                                                                                                            Рассмотрим ребро i->j. Т.к. все ребра имеют вид j/lp(j)->j, то можно записать i=j/lp(j) или j=lp(j)*i.


                                                                                                            Т.к. lp(j) — минимальный простой делитель, то можно обозначит его буквой p: j = p*i. Теперь применим Теорему 2.1 из статьи.


                                                                                                            j = p^k*q, p < lp(q). (*)


                                                                                                            Перепишем j = p*(p^(k-1)q). Отсюда следует, что i = p^(k-1)q. Рассмотрим lp(i). Если k=1, то lp(i) = lp(q), по (*) lp(q) > p, иначе lp(i) = p. Таким образом, lp(i) >= p.


                                                                                                            Все, мы доказали, что j=i*p, p — простое и p <= lp(i).


                                                                                                            Теперь докажем, что для любого простого p <= lp(i) есть такое ребро.
                                                                                                            Рассмотрим любое простое p <= lp(i). Пусть j=p*i. Тогда lp(j) = min(p, lp(i)) = p. Значит i=j/p = j/lp(j). По определению ребро в j из i есть.


                                                                                                            Утверждение 3: Если для некоторого i известны все простые числа до i и lp(i), то внутренний цикл в алгоритме переберет все ребра из вершины i и подсчитает lp для всех концов этих ребер.


                                                                                                            Доказательство

                                                                                                            Внутренний цикл для всех p<lp[i] считает lp[i*p]=p. По утверждению 2, i*p — это и есть все концы ребер, исходящих из вершины i. По определению, для ребра i->j: lp(j) = j/i = i*p/i = p. Значит lp[] подсчитано правильно для всех концов ребер из i.


                                                                                                            Утверждение 4: Алгоритм поддерживает следующий инвариант — после исполнения итерации внешнего цикла для некоторого i, подсчитаны lp[j] для всех составных чисел j, т.ч. входящее в него ребро исходит из вершин с номером не больше i. Так же подсчитаны все простые числа до i включительно.


                                                                                                            Доказательство

                                                                                                            По индукции при i=2 простое число 2 будет найдено. Потом внутренний цикл выполнится ровно один раз для p=2. По утверждению 2, это все ребра из вершины 2. Инвариант выполнен.


                                                                                                            Далее индукционный переход, пусть инвариант выполнен для i-1. Тогда при итерации i, если i составное, то есть ребро идущее в i и оно начинается где-то до i-1. По инварианту, lp[i] уже подсчитано и отлично от нуля. Иначе, если i простое, то lp будет 0 и алгоритм добавит i в простые.


                                                                                                            Далее, по индукционному предположению выполнено условие утверждения 3, значит внутренний цикл подсчитает lp() для всех концов ребер из i. Теперь инвариант выполнен и для i.


                                                                                                            Из утверждения 4 следует, что алгоритм работает корректно. Внешний цикл и условие до внутреннего цикла выполнятся O(n) раз. Согласно утверждению 3, инструкция во внутреннем цикле выполнится ровно столько раз, сколько ребер в графе. По утверждению 1, их O(n).

                                                                                                              0
                                                                                                              Для всех составных i проведем ребро из i/lp(i) в i.
                                                                                                              Конец ребра в i по построению: т.е. i/lp(i) — начало, i — конец, — ok. Но тогда: как возможно, что из i выходят ребра (т.е. i — начало)?:
                                                                                                              Утверждение 2: Из вершины i выходят ребра в вершины j = p*i,
                                                                                                              По построению в i ребра только входят (i всегда конечная вершина). Повторю цитату еще раз:
                                                                                                              проведем ребро из i/lp(i) в i.

                                                                                                              Предполагаю здесь конфликт имен, когда одинаковыми именами названы разные сущности. Вижу, что ранее я был недостаточно внимателен и только сейчас догадался, что разговор про орграф — теперь понял Ваше обозначение ребра типа i/lp(i)->i, т.е. ребро из x в y (x->y) и из y в x (y->x) — это разные ребра.
                                                                                                                0
                                                                                                                По построению в i ребра только входят (i всегда конечная вершина). Повторю цитату еще раз

                                                                                                                i — обозначает произвольную вершину. По определению графа, в нее входит одно ребро. Из нее могут выходить какие-то другие ребра. Там же в определении есть слова "для всех… i".


                                                                                                                Предполагаю здесь конфликт имен

                                                                                                                Формально это не конфликт, но если хотите — в определении графа используйте вместо i, допустим u. И не забудьте, что ребра есть для всех составных u.


                                                                                                                Приведу опять пример графа для n=10, чтобы понятнее было.


                                                                                                                Ребра 2->4, 3->6, 4->8, 3->9, 5->10. Упорядочены по концу, чтобы было видно, что для всех составных чисел есть одно входящее ребро.


                                                                                                                Тогда утверждение 2 говорит, что из вершины 2 должно выходить только ребро в 2*2=4. Из вершины 3, должны выходить ребра в 3*2 и 3*3 (потому что lp(3)=3 и есть 2 простых до 3). Из вершины 4, выходят ребра в 4*2 и все, потму что lp(4)=2. Из вершины 5 — одно ребро в 10, потому что дальше вершин нет.


                                                                                                                Утверждение 3 для i=3, наприер, говорит, что если нам даны простые числа {2, 3}, то выполнив внутренний цикл мы подсчитаем lp[6] и lp[9]. Действительно, посмотрите на код и выполните внутренний цикл при i=3, pr = {2,3} и lp[3]=3.

                                                                                                                  0
                                                                                                                  i — обозначает произвольную вершину.
                                                                                                                  Нет, Вы определили:
                                                                                                                  Для всех составных i


                                                                                                                  Давайте разименуем: пусть х любое из 2 до n.
                                                                                                                  Получаем:

                                                                                                                  Утверждение 2: Из вершины х выходят ребра в вершины j = p*i, т.ч. p — простое и p<= lp(i).

                                                                                                                  По построению мы знаем, что х= i/lp(i), j = i, т.к. только из i/lp(i) в i выходят ребра.

                                                                                                                  Получаем:

                                                                                                                  Утверждение 2: Из вершины i/lp(i) выходят ребра в вершины i = p*i, т.ч. p — простое и p<= lp(i).

                                                                                                                  i = p*i — абсурд.
                                                                                                                    0

                                                                                                                    Так, хорошо. Переименуйте в определении графа i в u.


                                                                                                                    Вы переименовали i вначале утверждения, но не в конце:


                                                                                                                    Утверждение 2: Из вершины х выходят ребра в вершины j = p*i, т.ч. p — простое и p<= lp(i).

                                                                                                                    Понятно, что у вас бред какой-то получается.

                                                                                                                      0
                                                                                                                      Переименуйте в определении графа i в u.
                                                                                                                      Извините, совсем не понял. Где определение графа? Вы это называете определением?:
                                                                                                                      Введем граф из n-1 вершин, пронумерованных от 2 до n.
                                                                                                                      Здесь нет i.
                                                                                                                        0
                                                                                                                        Извините, совсем не понял. Где определение графа?

                                                                                                                        Граф состоит из вершин и ребер. i участвует в определении ребер графа. Следующее предложение.

                                                                                                                        0
                                                                                                                        Предполагаю, что Вы хотите сказать:

                                                                                                                        Утверждение 2: Из вершины х=i/lp(i) выходят ребра в вершины j=i = p*u т.ч. p — простое и p<= lp(u).

                                                                                                                        Выше без изменений. Верно?

                                                                                                                          0

                                                                                                                          Нет. что вы тут вообще нагородили?! КАК?!


                                                                                                                          Еще раз, сначала. Определим граф из n-1 вершин. Для любой вершины с номером u, если u составное, то есть ребро u/lp[u]->u.


                                                                                                                          Утверждение 2 (Чуть более многословно, раз вам непонятно):


                                                                                                                          Рассмотрим некоторую вершину i. Если из нее есть какое-то ребро, в некоторую вершину j, то j= p*i, для некоторого простого p и p <= lp(i). И наоборот, для любого простого q <= lp(i), есть ребро i->q*i.

                                                                                                                            0
                                                                                                                            Только давайте будем спокойнее. Мы не обязаны этим заниматься и занимаемся для собственного удовольствия. Еще могу Вас успокоить: я реализовал этот алгоритм, убедился, что он работает так, как про него написано (что я и предполагал). Единственная проблема — это доказательство, и Вы в общем решили эту проблему — я ведь не говорю и не говорил, что Ваше доказательство никуда не годится. Очень даже годится, но ИМХО нуждается в чистке от неоднозначностей и шлифовке. Может Вам от формата обсуждения стоит перейти к формату статьи? Если нужна реализация — могу ее Вам выслать. BTW интересно, что несмотря на O(n) программа показала не самые быстрые результаты, чем в листинге 2 обсуждаемой здесь статьи: для n =100М — 1.109 сек., против 0.859 сек.
                                                                                        0
                                                                                        И как, скажите, пожалуйста, два вложенных друг в друга цикла (первый от 2 до n) могут дать линейное время?

                                                                                        Прежде всего возникает вопрос: а зачем тогда внутренний цикл?

                                                                                        Это довольно распространенная практика в некоторых алгоритмах, кроме РЭ приходят в голову метод двух указателей и алгоритм Кнута-Морриса-Пратта
                                                                              +1
                                                                              Вы можете ускорить альгоритм РЭ но это будет уже другой алгоритм. Да и вообще для чего? Он хорош для демострации школьникам, а на практике на столько дорог что скорее бесполезен. На практике встречаестся задача проверки некоего числа на простоту. Для этого есть другие алгоритмы, например Конягина-Померанса, Миллера и куча более дешевых вероятностных оценок. Задача изобрести большое простое число решается примено так, генерируем случайное число большой размерности, проверяем его простоту, повторяем.
                                                                                0
                                                                                Вы можете ускорить альгоритм РЭ

                                                                                Я не вижу, как это можно сделать. Попробуйте.
                                                                                Он хорош для демострации школьникам, а на практике на столько дорог что скорее бесполезен.

                                                                                Решето Эратосфена является популярным способом оценки производительности компьютера.

                                                                                0
                                                                                Пока, самую быструю реализацию на Python видел у ShashkovS в 2014 году.
                                                                                  0
                                                                                  Нет такой — м.б. в черновики удалил?
                                                                                  +1
                                                                                  Раз уж про меня вспомнили, то вот сравнение нескольких реализаций. На списках несколько геморройнее, зато в 3 раза быстрее.

                                                                                  Код на python
                                                                                  from timeit import timeit
                                                                                  
                                                                                  
                                                                                  def eratosthenes1(N):
                                                                                      simp, nonsimp = [2], set()
                                                                                      for i in range(3, N + 1, 2):
                                                                                          if i not in nonsimp:
                                                                                              nonsimp |= {j for j in range(3 * i, N + 1, 2 * i)}
                                                                                              simp.append(i)
                                                                                      return simp
                                                                                  
                                                                                  
                                                                                  def eratosthenes2(N):
                                                                                      simp, nonsimp = [2, 3], {i for i in range(3, N + 1, 3)}
                                                                                      for i in range(5, int(N ** 0.5), 2):
                                                                                          if i not in nonsimp:
                                                                                              nonsimp |= {j for j in range(i * i, N + 1, 2 * i)}
                                                                                              simp.append(i)
                                                                                      simp.extend([j for j in range(i, N + 1, 2) if j not in nonsimp])
                                                                                      return simp
                                                                                  
                                                                                  
                                                                                  def eratosthenes3(N):  # Возвращает список простых чисел от 2 до N
                                                                                      if N < 2:
                                                                                          return []
                                                                                      A = [False, True] * ((N + 2) // 2)
                                                                                      A[2] = True
                                                                                      for i in range(3, int(N ** 0.5 + 1.5), 2):
                                                                                          if A[i]:
                                                                                              for j in range(i * i, N + 1, 2 * i):
                                                                                                  A[j] = False
                                                                                      return [i for i in range(2, N + 1) if A[i]]
                                                                                  
                                                                                  # Самая быстрая версия, N = 10**8, ~13c
                                                                                  def eratosthenes4(N):  # Возвращает список простых чисел от 2 до N
                                                                                      if N < 2: return []
                                                                                      A = [False, True] * ((N + 2) // 2)  # Про чётные всё очевидно
                                                                                      simps = [2]
                                                                                      sqrtN = int(N ** 0.5 + 1.5)  # Корень плюс ещё немного
                                                                                      sqrtN += 1 - sqrtN % 2  # Делаем нечётным (это пригодится позже)
                                                                                      for i in range(3, sqrtN, 2):
                                                                                          if A[i]:
                                                                                              simps.append(i)
                                                                                              for j in range(i * i, N + 1, 2 * i):
                                                                                                  A[j] = False
                                                                                      simps.extend(i for i in range(sqrtN, N + 1, 2) if A[i])  # Вот здесь важно, что sqrtN нечётный
                                                                                      return simps
                                                                                  
                                                                                  
                                                                                  def eratosthenes5(n):  # Решето Грайса и Мисра (David Gries, Jayadev Misra), асимптотика O(n)
                                                                                      lsd = [0] * (n + 1)
                                                                                      simp = []
                                                                                      for i in range(2, n + 1):
                                                                                          if lsd[i] == 0:
                                                                                              simp.append(i)
                                                                                              lsd[i] = i
                                                                                          for p in simp:
                                                                                              if p * i > n:
                                                                                                  break
                                                                                              lsd[p * i] = p
                                                                                      return simp
                                                                                  
                                                                                  
                                                                                  funcs = [obj for name, obj in globals().items() if name.startswith('erat')]
                                                                                  N = 10 ** 8
                                                                                  setup = 'from __main__ import funcs, N'
                                                                                  for i in range(len(funcs)):
                                                                                      print(timeit(stmt='funcs[{}](N)'.format(i), setup=setup, number=1))
                                                                                  # 59.081
                                                                                  # 41.303
                                                                                  # 14.553
                                                                                  # 12.582 <- eratosthenes4 в 3+ раза быстрее
                                                                                  # 75.451
                                                                                  



                                                                                  А вот до кучи реализация на rust. У меня миллиард считает за 6с (ноутбучный core i5, 1.6GHz)
                                                                                  (third112)

                                                                                  Код eratosthenes4 на rust
                                                                                  use std::time::Instant;
                                                                                  
                                                                                  fn eratosthenes4(n: usize) -> Vec<usize> {
                                                                                      if n < 2 {
                                                                                          return Vec::new();
                                                                                      }
                                                                                      let mut tst = vec![true; (n + 1) / 2];
                                                                                      let mut simps = vec![2];
                                                                                      let mut sqrt_n = ((n as f64).sqrt() + 1.5) as usize;
                                                                                      sqrt_n += 1 - sqrt_n % 2;
                                                                                      for i in (3..sqrt_n).step_by(2) {
                                                                                          if tst[i>>1] {
                                                                                              simps.push(i);
                                                                                              for j in (i * i..(n + 1)).step_by(2 * i) {
                                                                                                  tst[j>>1] = false;
                                                                                              }
                                                                                          }
                                                                                      }
                                                                                      for i in (sqrt_n..(n + 1)).step_by(2).filter(|x| tst[x>>1]) {
                                                                                          simps.push(i);
                                                                                      }
                                                                                      return simps;
                                                                                  }
                                                                                  
                                                                                  
                                                                                  fn main() {
                                                                                      let now = Instant::now();
                                                                                      let n = 1_000_000_000;
                                                                                      let res = eratosthenes4(n);
                                                                                      let dur = Instant::now().duration_since(now);
                                                                                      println!("Duration: {:?}, len: {}", dur, res.len());
                                                                                      // Duration: 6.0877631s, len: 50847534
                                                                                  }
                                                                                  
                                                                                  

                                                                                    0
                                                                                    Спасибо. Интересно.
                                                                                  0

                                                                                    0
                                                                                    Только что набрел на эту тему и показалось, что на Питоне реализация слишком медленная.
                                                                                    Я делал так:
                                                                                    N = 10**8
                                                                                    
                                                                                    def er(n):
                                                                                        sz = n//2
                                                                                        sieve = bytearray(b'\x01'*sz)
                                                                                        for i in range (1, int(n**0.5)//2):
                                                                                            if (sieve[i]):
                                                                                                s = 2*i+1
                                                                                                p = 2*i*(i+1)
                                                                                                sieve[p::s] = [False]*((sz-p-1)//s+1)
                                                                                    #    return len(list(filter(None, sieve)))# if you need count of primes only, Time: 3.6 for N = 10**8
                                                                                        simp = [2]
                                                                                        simp.extend(2*i+1 for i in range(1, sz) if sieve[i])
                                                                                        return(simp)
                                                                                    
                                                                                    print(len(er(N)))
                                                                                    
                                                                                    # 5761455
                                                                                    # Time: 8.223
                                                                                    

                                                                                    Считает за 8 сек до 10**8 на i3, причем больше половины времени уходит на заполнение массива чисел.
                                                                                      +1
                                                                                      Добавил в стаью ссылку на статью о приведенном в Википедии алгоритме с «линейным временем работы».

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

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