Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?

[ananova]

venco в сообщении #298702 писал(а):

Уверяю Вас, вы не знаете такого способа.

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

[fer1800]

venco в сообщении #298702 писал(а):

ananova в сообщении #298610 писал(а):

Поэтому мне нужен единомышленник (единомышленники), которые могут вычислить праймориал больше чем 12 млн цифр.. Как тут посчитал venco - это несколько десятков мегабайт всего навсего.

Это довольно тривиальная задача. Произведение первых $10^7$ простых чисел (вплоть до $179424673$) считается за время меньше минуты.
В бинарном виде 32 мегабайта (выше я немного ошибся).
В десятичном виде $77919922$ цифр:
$3380445109538286518178...30065441278013328441066732954520433703644022980910$

Все простые числа считаются известными?
Каковы условия задачи? - уточните.

[ananova]

fer1800 в сообщении #298749 писал(а):

Все простые числа считаются известными?
Каковы условия задачи? - уточните.

Нет ничего проще - побить рекорд 2001 года для простых, равных значению праймориала+1.
Сложность заключается в проверке на простоту праймориала+1. Как показал venco - проблема только в этом.

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

Если найти "прорывной" способ определения на простоту, сравнимый с эффективностью проверки чисел Мерсенна, то можно и на большее замахнуться.

Но в этом я тоже стал сильно сомневаться.

[Someone]

Существует программа PrimeForm, приспособленная для сравнительно быстрой проверки на простоту больших чисел. К сожалению, не любых, но с числами вида $n\#\pm 1$ она справляется. Я не знаю, какая у неё верхняя граница, но с миллионом цифр она справляется, если хватит терпения и питание компьютера случайно не отключится. Однако для установления рекорда она не годится, а более быстрой программы я не знаю (программу, предназначенную для проверки специально чисел Мерсенна, не считаем).

[maxal]

Someone в сообщении #298827 писал(а):

Существует программа PrimeForm,

PrimeForm уже устарела - ее наследник OpenPFGW: http://sourceforge.net/projects/openpfgw/files/

[ananova]

Википедия сообщает:

Проект по проверке проблемы Гольдбаха сообщает, что были вычислены все простые числа до $10^{18}$. Это составляет 24 739 954 287 740 860 простых чисел, но они не были сохранены.

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

[Профессор Снэйп]

Someone в сообщении #298437 писал(а):

Количество цифр в десятичной записи данного числа.

Зачем десятичная, двоичную запись надо юзать!

Кстати, решето Эратосфена до каких чисел оказывается эффективным?

[lorents]

ananova в сообщении #298820 писал(а):

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

Есть детерминированный алгоритм проверки числа на простоту, с полиномиальной сложностью (праймориал +- 1 под него подходит).
Операций по сравнению с Мерсеновским алгоритмом будет больше в 4*(Количество простых в праймориале) раза.
А здесь его результаты:
http://dxdy.ru/post324691.html#p324691
http://dxdy.ru/post324794.html#p324794

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

Кто деньги пробьет под это дело?

[lorents]

lorents в сообщении #324997 писал(а):

Есть детерминированный алгоритм проверки числа на простоту, с полиномиальной сложностью (праймориал +- 1 под него подходит).
Операций по сравнению с Мерсеновским алгоритмом будет больше в 4*(Количество простых в праймориале) раза.

И еще, алгоритм детерминированной проверки чисел Мерсена, насколько я понимаю, не распараллеливается.
Если я прав, чтобы проверить число Мерсена $2^{43112609}-1$ надо выполнить 43112609 двойных операций (умножить, сложить) по модулю этого большого числа. Смотрите Тест Люка-Лемера на Википедии. Это делается на одном компьютере.

Предлагаемый алгоритм распараллеливается по количеству простых в праймориале.

[ananova]

lorents в сообщении #325041 писал(а):

И еще, алгоритм детерминированной проверки чисел Мерсена, насколько я понимаю, не распараллеливается.

алгоритм можно не распараллеливать, а оставить неизменным, а данные исходные разбить и куски их раздать друзьям по компьютерам. Кому повезёт, тот и герой!

[SerjeyMinsk]

ananova в сообщении #298429 писал(а):

100 байт займет одно простое число.

venco в сообщении #298490 писал(а):

100 бит, или 13 байт.

А сколько символов (цифр) в числе о котором Вы говорите?
Насколько знаю 1 байт - 1 символ.

[lorents]

SerjeyMinsk в сообщении #325410 писал(а):

ananova в сообщении #298429 писал(а):

100 байт займет одно простое число.

venco в сообщении #298490 писал(а):

100 бит, или 13 байт.

А сколько символов (цифр) в числе о котором Вы говорите?
Насколько знаю 1 байт - 1 символ.

Уважаемый, в одном байте 8 бит

[SerjeyMinsk]

lorents в сообщении #325465 писал(а):

SerjeyMinsk в сообщении #325410 писал(а):

ananova в сообщении #298429 писал(а):

100 байт займет одно простое число.

venco в сообщении #298490 писал(а):

100 бит, или 13 байт.

А сколько символов (цифр) в числе о котором Вы говорите?
Насколько знаю 1 байт - 1 символ.

Уважаемый, в одном байте 8 бит

И что?

[Xaositect]

SerjeyMinsk в сообщении #325468 писал(а):

И что?

10 бит - это примерно 3 десятичных цифры

[age]

ananova

Цитата:

Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?

1 HDD, если пользоваться архиватором.