|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
10.12.2018, 13:59 | #1 |
Спокойный псих
Участник клуба
Регистрация: 19.03.2013
Сообщений: 1,538
|
Где можно разжиться простыми числами ?
Здравствуйте.
Сегодня мне приспичило кое-что проверить, и я пошёл генерировать простые числа. И столкнулся с тем, что уже миллион простых чисел у меня генерируется порядка минуты (решето Эратосфена). Я же хочу "чем больше, тем лучше", и теоретический предел - 2^31-1, это максимально возможная длина массива (int). Практический же предел 2^30+2^29 (оперативная память). Для проверки при вычислениях использую ulong, что бы всем всего хватило, но не в этом проблема ... Здесь нашёл простые числа до 21 миллиона, и нужно так же потратить время на сбор этих чисел со всех страниц в одну кучу. И пока я их собираю - пришёл сюда узнать, где можно разжиться ещё числами ?
Подпись ? Не, не слышал ...
|
10.12.2018, 16:11 | #2 |
Участник клуба
Регистрация: 17.05.2011
Сообщений: 1,660
|
Попробовал сейчас простенькой программой "помайнить" простые числа от 2 до 60 000 000. Получилось записать в массив 3 562115 простых чисел за 48 сек.
Это в лоб, без всяких потоков. А если разделить на 4 ядра эти 60 миллионов, то думаю что за секунд 15 можно управиться. |
10.12.2018, 19:13 | #3 |
Старожил
Регистрация: 16.12.2011
Сообщений: 2,329
|
только сегодня! только для вас!
целый миллион простых чисел по символической цене - 200 руб. каждый десятый миллион - бесплатно! спешите! предложение ограниченно! |
10.12.2018, 23:19 | #4 |
Спокойный псих
Участник клуба
Регистрация: 19.03.2013
Сообщений: 1,538
|
kvitaliy, я так понимаю, вопрос об оптимизации алгоритма майнинга.
Я на хабре стырил алгоритм для C# (легко найти в гугле), он сам по себе до безобразия не оптимизирован, в изначальном виде уже 1000 чисел генерит за 10 секунд. Я его подшаманил, и получил свой миллион за минуту. Наверное лучше писать свой алгоритм, и не C#, а какой нибудь C++. Прикинул, только запись уже готовых чисел на HDD займёт ~3 минуты - это количество чисел 2^30+2^29 (6 гигабайт), при средней скорости записи 40 МБ/с. На SDD конечно будет быстрее писать.
Подпись ? Не, не слышал ...
|
10.12.2018, 23:21 | #5 |
Спокойный псих
Участник клуба
Регистрация: 19.03.2013
Сообщений: 1,538
|
_Bers, миллион я и сам могу сделать за минуту, а нужное мне кол-во выйдет в символическую копеечку - почти 290 000 рублей.
Подпись ? Не, не слышал ...
Последний раз редактировалось OmegaBerkut; 10.12.2018 в 23:43. |
10.12.2018, 23:42 | #6 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Для массива в полтора миллиарда простых чисел потребуется 12 гиг. Там ближе к краю этого массива скорее всего потребуется как минимум ulong для каждого такого числа )
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 10.12.2018 в 23:44. |
10.12.2018, 23:46 | #7 |
Спокойный псих
Участник клуба
Регистрация: 19.03.2013
Сообщений: 1,538
|
Аватар, 1 610 612 736 - максимальное значение, которое я смогу осилить. Как видно - оно замечательно влазит в Int32, и это НЕ количество простых чисел, а верхняя граница диапазона, из которого имеет смысл выбирать простые числа.
Хотя если помозговать, то можно и подогнать количество простых чисел в пределах Int32 - думаю можно из этого диапазона выбирать вообще все. Или из UInt32, для рассчётов всё равно всем всё хватит. Только вот при выборке непонятно как хранить весь диапазон ...
Подпись ? Не, не слышал ...
Последний раз редактировалось OmegaBerkut; 10.12.2018 в 23:54. |
10.12.2018, 23:49 | #8 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Ну а зачем тогда его весь на HDD, если нужны только простые? Хотя если для прямого доступа впоследствии, тогда есть смысл. Если не секрет - для чего?
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 10.12.2018 в 23:51. |
10.12.2018, 23:52 | #9 |
Спокойный псих
Участник клуба
Регистрация: 19.03.2013
Сообщений: 1,538
|
Аватар, хочу прогнать несколько паттернов, и проследить некоторые закономерности.
Подпись ? Не, не слышал ...
|
10.12.2018, 23:55 | #10 |
Спокойный псих
Участник клуба
Регистрация: 19.03.2013
Сообщений: 1,538
|
Можно же вообще не хранить числа в оперативной памяти, и по одному отправлять в поток записи ... Только для нахождения нужно проверять на делимость первые N/3+1
Подпись ? Не, не слышал ...
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
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 |