Нужна таблица простых чисел

[Ferma]

Нередко при анализе пользуюсь разложением числа на множители. Добрые люди прислали мне в распечатанном виде таблицу простых чисел до $10^6$. По интернету находил таблицу до миллиона триста тысяч. Нужна таблица до $10^12$. А на разложение числа ручным способом до корня квадратного уходит значительная часть времени. Малограмотный.

[Sonic86]

Посчитайте сначала, сколько терабайт она займет.

[Vince Diesel]

Матпакеты раскладывают. Конкретное число до $10^{12}$ - быстро.

[Руст]

До $10^{12}$ простых чисел имеется в количестве 37 607 912 018. При хранении 5 байтов на число это займет менее 200 Гб, не так много учитывая современные дмски.
Однако, кому нужно хранить такое количество в памяти. Для разложения больших чисел N (больше $2^{32}$) метод пробного деления на все простые $\sqrt N$ не эффективно.

Необходимость иметь такое количество простых появляется только если вы хотите взломать RSA и знаете, что одно из простых чисел в интервале $(N, N+10^{12}), N>10^{24}.$
Тогда для более эффективного нахождения заданного простого, можно действительно делить и исключать составные методом Эратосфена. Оставшиеся можно отфильтровать с проверкой на псевдопростоту (например по Эйлеру). Дальше не имеет смысла проверять на действительную простоту, проще сразу проверять на то, делить полученное число произведение простых или нет даже если это число имеет несколько тысяч битов.

[TOTAL]

(Оффтоп)

Руст в сообщении #704235 писал(а):

До $10^{12}$ простых чисел имеется в количестве 37 607 912 018. При хранении 5 байтов на число это займет менее 200 Гб, не так много учитывая современные дмски.

Ему нужна именно таблица. Т.е. все числа должны быть напечатаны на листах формата А4, которые затем сохранены в pdf- формате. А это больше, чем 200 Гб.

[ИСН]

(Оффтоп)

Значительная часть популярной литературы по арифметике посвящена объяснению того, как именно велики большие числа.
10 шрифт, 5 колонок, урезанные поля - у меня влезло 325 чисел на страницу. Если печатать с двух сторон, это примерно 100 000 пачек. 250 тонн. Несколько грузовиков бумаги.

[nnosipov]

ИСН в сообщении #704243 писал(а):

(Оффтоп)

Значительная часть популярной литературы по арифметике посвящена объяснению того, как именно велики большие числа.
10 шрифт, 5 колонок, урезанные поля - у меня влезло 325 чисел на страницу. Если печатать с двух сторон, это примерно 100 000 пачек. 250 тонн. Несколько грузовиков бумаги.

(Оффтоп)

Представил эту картину А вообще, понятно, ведь $10^{12}$ --- это всего лишь в два раза больше, чем $10^6$. Мне студенты говорили.

[TOTAL]

(Оффтоп)

nnosipov в сообщении #704263 писал(а):

А вообще, понятно, ведь $10^{12}$ --- это всего лишь в два раза больше, чем $10^6$. Мне студенты говорили.

$9^{12}$ нечетное, поэтому не может быть ровно в два раза больше, чем $9^6$.

[Sender]

Цитата:

Т.е. все числа должны быть напечатаны на листах формата А4, которые затем сохранены в pdf- формате. А это больше, чем 200 Гб.

Наверняка можно написать программу в PostScript, которая будет весить много меньше.

Более того, она уже кем-то написана и весит чуть больше килобайта. Верхняя граница поиска простых чисел задаётся в /max. Простые числа, не превышающие 10 миллионов, у меня сгенерировались за пару минут, заняв 831 страницу.