База данных простых чисел

Давеча снова увлекся простыми числами. Манит меня их тайна.

Написал алгоритм, похожий на решето Эратосфена. За 3 часа программа нашла 700 тысяч первых простых чисел. А мне надо хотя бы 14 миллионов простых чисел, чтобы перемножив их, получить число с количеством десятичных цифр, равным 100 миллионам штук.

Из статьи «Еще раз о поиске простых чисел», написанной пользователем Bodigrim, узнал о существовании быстрой программы primegen, которая работает используя решето Аткина. Установил ее в виртуальной машине LUbuntu (VirtualBox). Действительно, primegen очень быстро работает!

Тогда встал вопрос, как сохранить 14 миллионов простых чисел? Можно просто каждое простое число записать в файл как int32. А если простое число будет больше мощности 32-х бит?

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

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

В программе primegen в исходном файле primes.c вместо вывода числа на экран реализовал алгоритм подсчета статистики по кол-ву расстояний между числами:

 int RastCount_Index = 0;
 int RastCount[1000];
 for(i=0;i < 1000; i++) RastCount[i] = 0;

 for (;;) {
  u = primegen_next(&pg) - p;
  p += u;
  if (p > high) break;

  for (i = 0;u;++i)
   {
    u += digits[i];
    if (u >= 200)
     {
      digits[i] = u % 10;
      u = u / 10;
     }
    else
     {
      digits[i] = mod10[u];
      u = div10[u];
     }
   }
  if (i > len) len = i;
  int LetsRast, index;
  LetsRast = 0;  index = 0;
  char r[40], r_old[40];
  for (i = 0;i < 40; i++) { r[i] = 0; r_old[i] = 0; }

  for (i = len - 1;i >= 0;--i)
   {
    if (! LetsRast)
    if (digits_old[i] != digits[i]) LetsRast = 1;

    if (LetsRast)
     {
      r[index] = '0' + digits[i];
      r_old[index] = '0' + digits_old[i];
      index++;
     }
   }

  int ri, ri_old, Rast;
  ri = atoi(r);
  ri_old = atoi(r_old);
  Rast = (ri - ri_old) >> 1;
  RastCount[Rast]++;
  if (Rast > RastCount_Index) RastCount_Index = Rast;

  for (i = len-1;i >= 0; i--)
   digits_old[i] = digits[i];
 }

 for(i = 0; i <= RastCount_Index; i++)
  printf("%i = %i\n", i, RastCount[i]);


В терминале выполнил:

./primes 1 1000000000

Через 10 секунд отобразился список:
0 = 1 (расстояние между числами 2 и 3)
1 = 3424507

141 = 1

Таким образом, 141 — максимально-возможное расстояние по простое число значением до 1 миллиарда.

Написал код записи в файл:

FILE* fd;
fd = fopen("primes.bin", "w+");
unsigned char b1[1];
b1[0] = Rast;
fwrite(b1,1,1,fd);
fclose(fd);

Запустил до 300 миллионов:

./primes 1 300000000

В файле primes.bin получил 16 миллионов первых простых чисел. Сжал архиватором 7-Zip, файл ужался до 9 Мб.

P.S. Есть идея, как еще сильнее сжать БД простых чисел. Надо простые числа разделить на 4 группы по последней десятичной цифре: 1, 3, 7, 9. Расстояние между числами делить на 10. Так же сформировать 4 файла. При этом возможно, что для значений расстояния можно будет отвести не 8 бит, а меньше, тогда придется реализовать формирование байтового буфера из, например, 5-битных расстояний.

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

Ну. И что?
Реклама
Комментарии 58
    +7
    С ростом простых чисел, расстояние между ними постепенно увеличивается (вики). Когда встречается первый интервал больше 256 надо проверять. Так что такое сжатие допустимо только в определенных пределах.
      0
      После превышения 255 в файл пишется два байта: нулевой и байт, равный (расстояние — 255). Поскольку нулевое расстояние невозможно (сейчас нулевой байт в файле — это самый первый байт, но его можно убрать, чтобы не мешался), то нулевой байт как раз сигнализирует о более длинном расстоянии. Программа primegen ищет простые числа в диапазоне, поэтому можно вхолостую прокручивать ее, чтобы узнать расстояние для определенного диапазона.
        0
        Да, с таким расширением сохранять можно. Учитывая, что непосредственной адресации к номерам не нужно, так что не страшно, что длина данных в файле будет «плавать».
        +14
        До 10^9 интервалов >= 256 три штуки:
        436273009..436273291: 282
        649580171..649580447: 276
        944192807..944193067: 260
        Этот комментарий спонсирован PARI/GP, на котором это вычисляется в одну строчку за 20 секунд (из которых предвычисление таблицы занимает 4).
        default(primelimit,10^9);q=0;forprime(p=2,10^9,if(p-q>=256,print(q," .. ",p,": ",p-q));q=p)
          +6
          Автор хранит половину расстояния, поскольку все они четны. Поэтому указанные вами значения все еще будут помещаться в один байт.
          Плюсую PARI/GP.
            +3
            PARI/GP — клёвая штука! спасибо, заценил.
        • НЛО прилетело и опубликовало эту надпись здесь
            0
            Идея состоит в том, чтобы перемножить 14 миллионов первых простых чисел, прибавить 2. Убедиться, что последняя цифра не 5.
            Полученное число будет иметь остаток от деления на любое из первых 14 миллионов простых чисел, равное 2.
            То есть надо проверять делимость на числа после 14-миллионного простого числа, хотя до корня их гораздо больше, чем 14 миллионов.
            Хочу составить простое число размером в 100 миллионов разрядов и выиграть 150 тысяч долларов :) EFF Cooperative Computing Awards. Вот только как доказать, что оно простое, за разумное время?
            • НЛО прилетело и опубликовало эту надпись здесь
                +5
                Меня всегда это удивляло: статья начинается решетом эратосфена, а по итогу — попытка выиграть $150k, которые не могут взять профессиональные математики сидящие в датацентрах.
                0
                Алексей, а вы понимаете, что проверок делимости вам придется сделать не просто больше, чем 14 млн, а целых 10^50?

                Мой вам совет: не переводите время попусту.
                  +4
                  А вы прикинули сколько времени эти будут умножаться?

                  И зачем вам для этой задачи извращения с компактным хранением? 14 миллионов чисел, даже если взять 128 бит на число, будут занимать 224 мегабайта.
                    0
                    Идея понятна, сам подобным занимался.
                    Вопрос собственно только в том зачем вы вообще собрались хранить простые числа в БД да ещё в виде расстояний если единственное для чего они нужны — это получить их произведение???
                    Не проще ли вычислять простое число и сразу умножать его на предыдущие? И хранить нигде не надо будет.
                      –4
                      вообще-то надо признать двойку простым числом и к произведению прибавлять единицу. Полученное число не проверять — оно однозначно простое. Для начала можно ознакомиться с доказательством Эвклида бесконечности множества простых чисел. На мой взгляд — вообще самое элегантное из доказательств.
                        +4
                        Увы, проверять надо. Например, 2*3*5*7*11*13+1 = 59*509.
                          –2
                          господа, топик все таки математический. если я не прав — поправьте меня. Хотелось бы понимать к чему был минус.
                          упс. Признаю, за числа больше множителей не подумал.
                          0
                          А где будем хранить 10107.7 временных чисел? Ведь для проверки вашего полученного волшебного числа, вам нужно будет найти простые на диапазоне 2.7*108..Sqrt(N)
                            +6
                            очередной диванный математик не понимает, что такое 100 Миллионов разрядов))
                              +1
                              1) Последняя цифра будет не 5. Она точно будет равна 2, так как в произведении будут присутствовать множители 2 и 5, что даст нам один ноль в десятичной записи.
                              2) Нет, остаток от деления на 2 будет равен 0, поэтому число будет составным.
                                +1
                                В произведении я не буду использовать числа 2 и 5 :)
                                  +2
                                  Последняя цифра точно будет 7, поскольку вы нечетное число умножаете на 5 (последняя цифра 5) и прибавляете 2.
                                    0
                                    Действительно, спасибо за уточнение.
                                +1
                                Это не способ получить длинное простое число.
                                2*3*5*7+2 делится на 2.

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

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

                                Как уже написали, не переводите время попусту. Потратьте его лучше на углубленное изучение теории чисел.
                                  +1
                                  Формула может быть двух видов:
                                  1) P+1, где в P используется множитель 2.
                                  2) P+2, где в P НЕ используется множитель 2.
                                  Доказательство Евклида вполне логичное. Сначала он принял на веру некоторое утверждение, затем пришел к противоречию, вывод: изначальное утверждение неверно. Знать значение простого числа в качестве делителя для каждого (произведения плюс 1) нет смысла: достаточно знать, что оно существует, что и показано Евклидом.
                                  +1
                                  А почему вы решили, что такое число будет простым?

                                  Смотрите, считаем произведение в Maxima:

                                  (%i1) 3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71+2;
                                  (%o1) 278970415063349480483707697

                                  Видим, что последняя цифра не 5.

                                  Теперь факторизуем:

                                  (%i2) factor(3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71+2);
                                  (%o2) 107 229 2832808637 4019033726627

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

                                  Так что для проверки простоты 100M значного числа вам нужно его факторизовать. Вы к этому готовы?
                                    +1
                                    Подобное число либо будет простым, либо при переборе делителей разделится без остатка, разумеется, этот делитель будет больше любого простого числа из множителей. Так-то понятно, что задумка нереальная, ну хоть скиллы прокачаю, а то для меня даже дельта-кодирование было откровением :)
                                    +1
                                    Хорошо, когда у задачи есть цель в виде чисел с плавающей точкой в базе данных какого-нибудь европейского банка. Это придает сил…
                                  0
                                  Чего-то я не понимаю. Вот обычное решето Эратосфена: pastebin.com/ck9kuEMg
                                  700к считает примерно за секунду (нужно взять хотя бы 15М чисел).
                                  20М считает секунд за 40.
                                  Вывод не считаю, поскольку не зависит от алгоритма. Зачем решето Аткина?
                                  +12
                                  > А расстояние между соседними простыми числами всегда должно быть небольшим, предположил, что уместится в один байт.

                                  смелое предположение.
                                    +2
                                    ага, возьмите лучше два.
                                    +2
                                    Меня вот только начальные данные смутили… В смысле, то что 700тыс. чисел вы считали аж 3 часа, при этом не когда-то давно, а буквально «давеча». Разве что на бейсике, нет?

                                    У меня просто аналогичная задача стояла лет 10 назад, ещё во времена модемного интернета. Хотелось насчитать праймов для хэш-таблички. Компы были ещё 32-битными, так что больше было не нужно. Я просто взял блоб на 512Мб и считал в нём битмаской (как раз 2^32 бит) решетом Эратосфена. На 1-поточном 32-битном 4-м пентиуме это заняло какое-то незначительное время (то ли 5, то ли 10 минут, а возможно и намного меньше — за давностью лет уже не помню). Но никак не 3 часа! Потому собственно, и удивляюсь: как так?

                                    (ЗЫ: по итогу мне нужны были не все числа, а с шагом увеличения в 1.2 раза. Потому вывод дополнительно проредил и табличку потом поместил в код хэша)
                                      0
                                      Какие похожие у нас комментарии :) мой ниже
                                      +5
                                      > Таким образом, 141 — максимально-возможное расстояние по простое число значением до 1 миллиарда.
                                      Вы, наверное, хотели сказать, что 282 (вдвое большее) — максимальное возможное расстояние.

                                      Первое число, для которого половина расстояния между простыми перестанет помещаться в один байт, — это 304 599 508 537. Его разность со следующим простым равна 514.

                                      По-английски это называется prime gap и им посвящена обширная литература. Можно начать хотя бы с википедии.
                                        +3
                                        «Есть идея, как еще сильнее сжать БД простых чисел» © Хранить их в виде программы, которая их вычисляет. Тогда можно все простыe, меньшие n, запаковать в архив длины O(log n). Фантастическое, экспоненциальное сжатие данных!

                                        Я намекаю на то, что чем более хитрый алгоритм сжатия вы придумаете (с разделение на файлы, с хранением разных видов разностей, разделенных на что-нибудь), тем дольше будет длиться распаковка вплоть до того момента, когда она сравняется с вычислением простых чисел на лету при помощи primegen.
                                          +1
                                          (сорри, промахнулся веткой)
                                          Интересно, как же решето получилось так неудачно?
                                          Код на питончике
                                          def eratosthenes(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
                                          print(len(eratosthenes(11 * 10 ** 6)))
                                          

                                          делает 726517 простых секунд за 30.
                                            0
                                            Насколько я понимаю Python, у вас реализовано не решето Эратосфена (сложность N log log N), а что-то порядка N^2, из-за того, что операция объединения множеств |= занимает линейное время по каждому из аргументов.
                                              0
                                              Операция |= занимает время порядка N / 2i (количество элементов в добавляемом множестве).
                                              В питоне операции с множествами имеют O(1).

                                              N^2 на 11 миллионах замер бы навсегда…
                                                0
                                                Вероятно, вы правы. Но тогда почему в пайтон-вики (ссылка в предыдущем комментарии) пишется иное?
                                                Вы уверены, что после |= не приходится реаллоцировать все множество на новое место в памяти или что-нибудь в этом роде?
                                                  +2
                                                  Там всё устроено следующим образом: в питоне множества — это хеш-таблицы. Сначала создаётся таблица на 16 элементов. По заполнении 2/3 происходит реаллокация с увеличением размера в 4 раза. По достижении размера в 32768 таблица не учетверяется, а удваивается. Таким образом у нас будет O(log n) реаллокаций. Практически все они произойдут в момент добавления нечётных чисел, делящихся на три. То есть мы сразу фигакаем хеш-таблицу на 2^(log(N/6) + 1) элементов, а дальше её потихоньку заполняем и другими не-простыми.
                                                    +1
                                                    Посмотрел в вики. Если было бы написано
                                                    nonsimp = nonsimp | {j for j in range(3 * i, N + 1, 2 * i)}
                                                    то было бы O(сумма элементов там и там)

                                                    Но мы подливаем в существующее множество, поэтому имеем O(количество добавляемых элементов)
                                                      +1
                                                      Спасибо за развернутый комментарий; простите, что морочил голову.
                                                0
                                                Самое неправильное — это использование хэша вместо массива. Асимптотика, конечно, у них обоих O(1), но константы очень сильно разные.
                                                По мелочи:
                                                — вычёркивание, начинающееся с 3 * i, теряет кучу времени, повторяя заведомо уже вычеркнутое до i * i,
                                                — после того, как i достигнет корня из N, операция |= вообще молотит вхолостую.
                                                import array
                                                def eratosthenes(N):
                                                    # nonsimp[j] corresponds to 2j+1
                                                    simp, nonsimp = [2], array.array('b', [0 for i in xrange((N + 1) // 2)])
                                                    i = 3
                                                    while i * i <= N:
                                                        if not nonsimp[(i - 1) // 2]:
                                                            for j in xrange((i * i - 1) // 2, (N + 1) // 2, i):
                                                                nonsimp[j] = 1
                                                            simp.append(i)
                                                        i += 2
                                                    simp.extend([2 * j + 1 for j in xrange((i - 1) // 2, (N + 1) // 2) if not nonsimp[j]])
                                                    return simp
                                                print(len(eratosthenes(11 * 10 ** 6)))
                                                  0
                                                  Действительно, про i * i я не задумывался. Про корень из N я забил, в питоне оно слабо влияет на время.

                                                  константы очень сильно разные

                                                  У меня для вас плохие новости: ваш алгоритм быстрее всего в два раза…
                                                  А после оптимизаций аналогичных вашим на моём компе 2.9с к 2.3с.

                                                  В целом вы правы, константы разные, но прикол в том, что в питоне множества и словари молниеносно быстры, в то время как обычная арифметика не так, чтобы летает (по сравнению с сями). Поэтому если цель сделать что-то быстро, то нет нужды заморачиваться.
                                                    0
                                                    А после оптимизаций аналогичных вашим на моём компе 2.9с к 2.3с.

                                                    А покажите версию после оптимизаций, интересно.
                                                      +2
                                                      def eratosthenes(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
                                                      print(len(eratosthenes(11 * 10 ** 6)))
                                                      


                                                      Там есть ещё возможности оптимизировать, но они дурацкие и дают малый прирост.
                                                0
                                                Мне нравится такой подход: программа (зачастую стороннее ПО) выполняет свою работу, результатом ее работы должен стать, например, файл. После чего эта программа уже не нужна. С полученным файлом можно работать, используя другое ПО. Таким образом получается пошаговое получение результатов.
                                                То есть разработчик не связан какой-то тучей программ, программа выдала результат, он сохранил результат и забыл про нее, сосредоточился на дальнейшем решении задач. И вот так, маленькими шажками, как маленький ребенок :)
                                                0
                                                А можно для каждого числа сохранять количество делителей, отличающихся от единицы и самого числа. Простые числа — это частный случай с таким количеством делителей равным нулю.
                                                Вообще интересно построить какие-нибудь графики по этим данным… например чтобы увидеть, как количество простых чисел уменьшается с увеличением x…
                                                y=количество_простых_чисел_до(x)
                                                по идее должно быть что-то типа sqrt(x)
                                                ну и дальше поиграть с масштабами, чтобы понять что за кривая.
                                                +11
                                                В чем смысл статьи?
                                                Автор открыл для себя дельта-кодирование?

                                                2/3 текста занимает листинг программы, считающей (обожемой) статистику по расстоянию между соседними простыми числами. Зачем он? Кому он может оказаться полезен?

                                                В чем состоит тайна простых чисел, анонсированная в первой строке? В том, что они… хммм… простые?

                                                И, наконец, при чем тут вообще Big Data?

                                                Детский сад какой-то, чесслово.
                                                  +5
                                                  Зато из комментариев я, например, узнал о PARI/GP :)
                                                    0
                                                    Да! Я тоже полез про него читать :)
                                                  0
                                                  Тогда встал вопрос, как сохранить 14 миллионов простых чисел?

                                                  Можно же использовать длинную арифметику. Это же проще, поддерживается в ряде языков (Java, .Net). Да, вычисления могут быть чуть дольше. Зато код сократится.
                                                    0
                                                    del
                                                      –3
                                                      Пусть это здесь полежит:

                                                      gmplib.org/

                                                      github.com/libtom/libtommath

                                                      github.com/infusion/PHP/tree/master/ext/bcmath/libbcmath (хоть и лежит в дистрибутиве php, вполне самостоятельна)
                                                        0
                                                        700к чисел за 3 часа — это на телефоне что ли считалось?

                                                        Я простыми числами интересовался лет 10 назад (на совершенно дилетантском уровне), когда у меня был Celeron-667 со 128 метрами памяти — и именно память меня лимитировала, поскольку уход в своп катастрофически снижал скорость. Но если не превышать, все считалось быстро.

                                                        Ну в общем, я считал решето Эратосфена, в котором каждое число было битом, причем за пропуском четных, как заведомо не простых. То есть число не кодировалось непосредственно, а задавалось позицией в массиве. В каждом байте таким образом содержалось 16 чисел, в каждом int — 64 числа. И бегал я по этому массиву Битовыми масками.

                                                        Точную производительность уже не помню, есессно, но ни про какие 3 часа речи не шло. Несколько минут может. Это на той технике.
                                                          0
                                                          Я бы порекомендовал автору всесторонне изучить сайт Kim Walisch — primesieve
                                                          Fast C/C++ prime number generator — и код самой primesieve; реализация шикарная, полированная, ибо человек лет 15 серьезно этим вопросом занимается
                                                          . Работает primesieve с сумасшедшей производительностью даже на настольном скромном тазике, а подробности реализации сегментированного решета и wheel факторизации полностью документированы. Однако, он явным образом пишет, что «primesieve can generate primes and prime k-tuplets up to 2^64» и всё, край географии. Интересно, почему. Наверное он просто такой задачи себе не ставил, сделать больше.

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

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