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

[arno1251.livejournal.com]

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

Comments

[santeros.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 мегабайт. Можно посчитать совсем точно, там даны значения для всех степеней десятки вплоть до миллиарда.
Свою программу я вовремя остановил :)

[milgrig.livejournal.com]

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

[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 секунд.