простые числа

[arno1251.livejournal.com]

Тут на башорге случайно обнаружили, что сумма всех простых чисел меньших миллиона является простым числом. А у меня попутно возник такой вопрос. Берём все простые числа, меньшие миллиарда (10⁹), и тупо записываем их в текстовый файл, разделяя LF:
2
3
5
7
11 etc.
Каким будет объём этого файла?
А если его сжать RARом?

Comments

[santeros.livejournal.com]

напиши прогу, которая создает файл бла-бла-бла и посмотри

hate brute force

[arno1251.livejournal.com]

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

Re: hate brute force

[true-poser.livejournal.com]

Брутфорс наше фсио.
Лям - 538468
10 лям -
Дальше задолбало.

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

Re: hate brute force

[arno1251.livejournal.com]

Разумно, спасибо.

[ipavel.livejournal.com]

лучший друг человека - эксперимент

[netp-npokon.livejournal.com]

Википедия говорит (http://en.wikipedia.org/wiki/Prime-counting_function), что pi(10⁹) = 50,847,534
Умножая на 10 (в среднем 9 знаков плюс \n) получим примерно 500 мегабайт. Можно посчитать совсем точно, там даны значения для всех степеней десятки вплоть до миллиарда.
Свою программу я вовремя остановил :)

[arno1251.livejournal.com]

Спасибо, это практически то, что мне хотелось узнать!

[pequeno-raposa.livejournal.com]

И если считать, что цифры в таком файле будут идти в случайном порядке, архиватор вроде как сожмет его до объема Ln(11)/Ln(2)/8 = 43% от первоначального.

[netp-npokon.livejournal.com]

Это, кстати, интересный вопрос, как будут распределены символы в выходном файле.

n=1000
0:15 (2%) 1:78 (12%) 2:32 (4%) 3:75 (11%) 4:34 (5%) 5:33 (5%) 6:33 (5%) 7:78 (12%) 8:30 (4%) 9:67 (10%) \n:168 (26%) total:643 (100%)

n=10000
0:232 (3%) 1:681 (11%) 2:391 (6%) 3:677 (11%) 4:360 (6%) 5:360 (6%) 6:369 (6%) 7:652 (10%) 8:351 (5%) 9:646 (10%) \n:1229 (20%) total:5948 (100%)

n=100000
0:2725 (4%) 1:6353 (11%) 2:3906 (6%) 3:6229 (11%) 4:3772 (6%) 5:3816 (6%) 6:3741 (6%) 7:6172 (10%) 8:3690 (6%) 9:6130 (10%) \n:9592 (17%) total:56126 (100%)

n=1000000
0:30350 (5%) 1:59634 (11%) 2:39572 (7%) 3:58770 (10%) 4:39006 (7%) 5:38911 (7%) 6:38714 (7%) 7:58327 (10%) 8:38541 (7%) 9:58145 (10%) \n:78498 (14%) total:538468 (100%)

n=10000000
0:324133 (6%) 1:570157 (10%) 2:400626 (7%) 3:564650 (10%) 4:397474 (7%) 5:396016 (7%) 6:395621 (7%) 7:560506 (10%) 8:394398 (7%) 9:558956 (10%) \n:664579 (12%) total:5227116 (100%)

Судя по всему, цифры все-таки появляются не с равными вероятностями. Хотя улучшить оценку на этом трудно.

[eterevsky.livejournal.com]

Цифры получаются с неравной вероятностью только за счёт старшей и младшей цифр. Дело в том, что плотность простых чисел между 9*10^n и 10^(n+1) заметно меньше, чем плотность простых чисел между 10^n и 2*10^n. (Это что касается старшей цифры.) Кроме того, простое число не может заканчиваться на чётную цифру и на 5. Вероятность нуля наименьшая, так как он не может стоять ни в первой, ни в последней позиции.

[arno1251.livejournal.com]

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

[ex-andrey-t.livejournal.com]

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

[pequeno-raposa.livejournal.com]

Текстовые файлы хорошо жмутся, потому что там большой избыток информации. Если же текстовый файл будет содержать случайную последовательность букв и цифр (допустим для простоты, что всего 32 различных символа), он сожмется всего лишь до 5/8 = 62.5% изначального объема.

[milgrig.livejournal.com]

1 - не простое число!

[arno1251.livejournal.com]

Хотите флейм тут развести?

[eterevsky.livejournal.com]

Тут нет места для флейма. 1 -- действительно по определению не является простым числом.

[arno1251.livejournal.com]

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

[jewgeniusz.livejournal.com]

Ну, казалось бы, на этот вопрос уже ответил Адамар больше ста лет назад. Ответ такой: что простых чисел, меньших N, примерно N/ln N. ("Примерно" значит "в пределе при N\to\infty").

Соответственно, ответ про миллиард можно посчитать устно -- 10^9/ln(10^9) = 10^9/(9\ln 10). Логарифм десяти чуть больше двух (посчитал на калькуляторе -- 2,3), то есть получается приблизительно 10^9/20=5 x 10^7. То есть простых чисел до миллиарда примерно 50 миллионов.

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

[eterevsky.livejournal.com]

Получившийся файл занимает 895 мегабайт (или, если быть точным 937484026 байт).

Заархивированный bzip2 (rar у меня нету) файл занимает 261 мегабайт (272893457 байт).

Время написания програмы с простым решетом Эратосфена -- 5-10 минут (не засекал). Время работы -- 46 секунд (с учётом вывода результатов). Время работы архиватора -- 3 минуты 37 секунд.

[arno1251.livejournal.com]

Спасибо огромное! Замечательно. Но немного не понял, откуда 895 мегабайт. Верхняя оценка получилась 500 мегабайт, если не врёт Википедия.

[eterevsky.livejournal.com]

Есть же хорошая поговорка: "Поспешишь -- людей насмешишь". Вот я и поспешил. =) После исправления бага в программе файл получился размером 479 мегабайт (сжатый -- 149 мегабайт). На всякий случай привожу здесь всю программу:

#include <math.h>
#include <stdio.h>
#include <string.h>

#define N 1000000000

char p[N/2];

int main() {
  memset(p, 1, N/2);
  p[0] = 0;
  int s = (int)sqrt(N) / 2 + 1;
  for (int i = 1; i < s; i++)
    if (p[i]) {
      int m = 2*i + 1;
      
      for (int j = (m*m - 1)/2; j < N/2; j += m)
        p[j] = 0;
    }
  
  printf("%d\n", 2);
  
  for (int i = 1; i < N/2; i++)
    if (p[i])
      printf("%d\n", 2*i+1);
}