Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.12.2018, 13:59   #1
OmegaBerkut
Спокойный псих
Участник клуба
 
Аватар для OmegaBerkut
 
Регистрация: 19.03.2013
Сообщений: 1,538
По умолчанию Где можно разжиться простыми числами ?

Здравствуйте.
Сегодня мне приспичило кое-что проверить, и я пошёл генерировать простые числа. И столкнулся с тем, что уже миллион простых чисел у меня генерируется порядка минуты (решето Эратосфена).
Я же хочу "чем больше, тем лучше", и теоретический предел - 2^31-1, это максимально возможная длина массива (int).
Практический же предел 2^30+2^29 (оперативная память).
Для проверки при вычислениях использую ulong, что бы всем всего хватило, но не в этом проблема ...
Здесь нашёл простые числа до 21 миллиона, и нужно так же потратить время на сбор этих чисел со всех страниц в одну кучу. И пока я их собираю - пришёл сюда узнать, где можно разжиться ещё числами ?
Подпись ? Не, не слышал ...
OmegaBerkut вне форума Ответить с цитированием
Старый 10.12.2018, 16:11   #2
kvitaliy
Участник клуба
 
Регистрация: 17.05.2011
Сообщений: 1,660
По умолчанию

Попробовал сейчас простенькой программой "помайнить" простые числа от 2 до 60 000 000. Получилось записать в массив 3 562115 простых чисел за 48 сек.
Это в лоб, без всяких потоков. А если разделить на 4 ядра эти 60 миллионов, то думаю что за секунд 15 можно управиться.
kvitaliy вне форума Ответить с цитированием
Старый 10.12.2018, 19:13   #3
_Bers
Старожил
 
Регистрация: 16.12.2011
Сообщений: 2,329
По умолчанию

только сегодня! только для вас!
целый миллион простых чисел по символической цене - 200 руб.

каждый десятый миллион - бесплатно!

спешите! предложение ограниченно!
_Bers вне форума Ответить с цитированием
Старый 10.12.2018, 23:19   #4
OmegaBerkut
Спокойный псих
Участник клуба
 
Аватар для OmegaBerkut
 
Регистрация: 19.03.2013
Сообщений: 1,538
По умолчанию

kvitaliy, я так понимаю, вопрос об оптимизации алгоритма майнинга.
Я на хабре стырил алгоритм для C# (легко найти в гугле), он сам по себе до безобразия не оптимизирован, в изначальном виде уже 1000 чисел генерит за 10 секунд. Я его подшаманил, и получил свой миллион за минуту.
Наверное лучше писать свой алгоритм, и не C#, а какой нибудь C++.
Прикинул, только запись уже готовых чисел на HDD займёт ~3 минуты - это количество чисел 2^30+2^29 (6 гигабайт), при средней скорости записи 40 МБ/с. На SDD конечно будет быстрее писать.
Подпись ? Не, не слышал ...
OmegaBerkut вне форума Ответить с цитированием
Старый 10.12.2018, 23:21   #5
OmegaBerkut
Спокойный псих
Участник клуба
 
Аватар для OmegaBerkut
 
Регистрация: 19.03.2013
Сообщений: 1,538
По умолчанию

_Bers, миллион я и сам могу сделать за минуту, а нужное мне кол-во выйдет в символическую копеечку - почти 290 000 рублей.
Подпись ? Не, не слышал ...

Последний раз редактировалось OmegaBerkut; 10.12.2018 в 23:43.
OmegaBerkut вне форума Ответить с цитированием
Старый 10.12.2018, 23:42   #6
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Для массива в полтора миллиарда простых чисел потребуется 12 гиг. Там ближе к краю этого массива скорее всего потребуется как минимум ulong для каждого такого числа )
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 10.12.2018 в 23:44.
Аватар вне форума Ответить с цитированием
Старый 10.12.2018, 23:46   #7
OmegaBerkut
Спокойный псих
Участник клуба
 
Аватар для OmegaBerkut
 
Регистрация: 19.03.2013
Сообщений: 1,538
По умолчанию

Аватар, 1 610 612 736 - максимальное значение, которое я смогу осилить. Как видно - оно замечательно влазит в Int32, и это НЕ количество простых чисел, а верхняя граница диапазона, из которого имеет смысл выбирать простые числа.
Хотя если помозговать, то можно и подогнать количество простых чисел в пределах Int32 - думаю можно из этого диапазона выбирать вообще все. Или из UInt32, для рассчётов всё равно всем всё хватит. Только вот при выборке непонятно как хранить весь диапазон ...
Подпись ? Не, не слышал ...

Последний раз редактировалось OmegaBerkut; 10.12.2018 в 23:54.
OmegaBerkut вне форума Ответить с цитированием
Старый 10.12.2018, 23:49   #8
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Ну а зачем тогда его весь на HDD, если нужны только простые? Хотя если для прямого доступа впоследствии, тогда есть смысл. Если не секрет - для чего?
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 10.12.2018 в 23:51.
Аватар вне форума Ответить с цитированием
Старый 10.12.2018, 23:52   #9
OmegaBerkut
Спокойный псих
Участник клуба
 
Аватар для OmegaBerkut
 
Регистрация: 19.03.2013
Сообщений: 1,538
По умолчанию

Аватар, хочу прогнать несколько паттернов, и проследить некоторые закономерности.
Подпись ? Не, не слышал ...
OmegaBerkut вне форума Ответить с цитированием
Старый 10.12.2018, 23:55   #10
OmegaBerkut
Спокойный псих
Участник клуба
 
Аватар для OmegaBerkut
 
Регистрация: 19.03.2013
Сообщений: 1,538
По умолчанию

Можно же вообще не хранить числа в оперативной памяти, и по одному отправлять в поток записи ... Только для нахождения нужно проверять на делимость первые N/3+1
Подпись ? Не, не слышал ...
OmegaBerkut вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Maple Арифметическая прогрессия с простыми числами Nadiya17 Помощь студентам 0 20.04.2013 10:17
задача с простыми числами Depolo Паскаль, Turbo Pascal, PascalABC.NET 4 18.11.2012 15:17
Программа с простыми числами VL@D1M1R Помощь студентам 13 21.01.2010 15:04
Задача на матрицу с простыми числами Dead Romantic Помощь студентам 6 25.12.2009 18:42