ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
25 сообщений из 402, страница 5 из 17
  5  все
Генератор простых чисел (до 10^9 за 5 сек)
    #38924227
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonНам полюбому нужен сценарий теста. Хорошо-бы чтоб все утилиты в STDOUT сбрасывали результат
по ключу.
Не писать не вариант, компилятор просто выкинет ненужный код и получишь нездоровые замеры.
Писать в STDOUT - тормоза от printf() не дадут нормально скорость измерить.
Я вектор использую, тоже не совсем корректно, память довыдедеряет, хотя это достаточно быстро, но вообще-то уже С++, а не С.

Предлагаю изолировать расчет от хранения результатов. Передавать в параметрах функцию void prime_store(uint64_t x), а дальше подсовывай что хочешь: хоть заглушку со счетчиком, хоть вектор. Пусть только верхний уровень знает что подсунул, а нижний честно ее вызывает.
Можно делать вычисления отдельным модулем. Функция. Класс. Компонента.
...
Рейтинг: 0 / 0
01.04.2015, 19:54
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924233
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TPS Дурной день был, умотался, все что наобещал сегодня не успею, завтра зафиксирую свои поделки.
Да бох с ним. Я не тороплю. Этот проект - Just For Fun.
...
Рейтинг: 0 / 0
01.04.2015, 20:01
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924252
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Мужики,

мне кажется до определённого размера простые числа можно не хранить, достаточно перебора

999999937 / 50847534 =19.6

вот смотрите, при натуральном k

6k-1
6k - кратно 2 и 3
6k+1
6k+2 - кратно 2
6k+3 - кратно 3
6k+4 - кратно 2

т.е. все простые числа лежат в множестве 6k+/-1, достаточно проверять 1 из 3-х чисел
операции с регистрами гораздо быстрее чем попытки лезть в память
...
Рейтинг: 0 / 0
01.04.2015, 20:29
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924255
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)все простые числа лежат в множестве 6k+/-1
Сходу могу сказать что ты масштабнее Аткина в 102,4 раза :) У того магическое число было 60.

Давай, развивай свою идею до примера кода который можно запустить.
...
Рейтинг: 0 / 0
01.04.2015, 20:36
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924263
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Мысль: у биткарты есть один большой недостаток, надо перебрать ее целиком чтобы результат получить. Вот бы взамен что-нибудь такое задействовать что быстро инициализируется, быстро убирает лишнее и быстро считывает остатки.
...
Рейтинг: 0 / 0
01.04.2015, 20:48
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924266
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan), добавлю инфы.

Это называется Спираль Улама.



На ней чёрными точками обозначены primes - белыми все остальные составные числа.
При условии что заполнение шло от центра квадрата против часовой стрелки.

На спирали отчётливо виден ближний порядок точек. По сути каждая точка
в ряду отстоит от другой на строго фиксированное расстояние
которое квадратично зависит от "витка спирали".

По сути картинка наглядно показывает что существует формула
описывающая "возникновение" следующей точки в ряду.

Весь вопрос в том насколько далеко распространяется
такой порядок.
...
Рейтинг: 0 / 0
01.04.2015, 20:55
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924272
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TМысль: у биткарты есть один большой недостаток, надо перебрать ее целиком чтобы результат получить. Вот бы взамен что-нибудь такое задействовать что быстро инициализируется, быстро убирает лишнее и быстро считывает остатки.
Это основной дефект Эратосфена. Нам недостаточно иметь карту простых. Нам
нужен итератор. А он к сожалению не очень эффективен. И не очень компактен.
...
Рейтинг: 0 / 0
01.04.2015, 21:03
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924281
-
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
-
Гость
maytonkealon(Ruslan), добавлю инфы.

Это называется Спираль Улама.

https://ru.wikipedia.org/wiki/Скатерть_Улама .
...
Рейтинг: 0 / 0
01.04.2015, 21:23
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924293
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima Tkealon(Ruslan)все простые числа лежат в множестве 6k+/-1
Сходу могу сказать что ты масштабнее Аткина в 102,4 раза :) У того магическое число было 60.

Давай, развивай свою идею до примера кода который можно запустить.
залейте исходники рабочие того что есть, что бы сравнивать можно было
сюда же вроде как решились лить?
...
Рейтинг: 0 / 0
01.04.2015, 21:59
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924301
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Это кому как удобно.
...
Рейтинг: 0 / 0
01.04.2015, 22:10
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924372
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima Tkealon(Ruslan)все простые числа лежат в множестве 6k+/-1
Сходу могу сказать что ты масштабнее Аткина в 102,4 раза :) У того магическое число было 60.

Давай, развивай свою идею до примера кода который можно запустить.

Марк, товарищ привел известный факт, не более ни менее. а 60 скорее всего получено эмпирически, других предположений пока нет, кроме мистицизма об делимости на числа от 1 до 6 ;)
...
Рейтинг: 0 / 0
02.04.2015, 01:52
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924392
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
А обязательно устанавливать ту программу для совместной работы с репозиторием ? Только через 7 часов смогу этим заняться
...
Рейтинг: 0 / 0
02.04.2015, 06:18
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924398
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryА обязательно устанавливать ту программу для совместной работы с репозиторием ? Только через 7 часов смогу этим заняться
Оттуда брать можешь без нее, но обратно что-то заливать без нее не получится. С ней удобнее, меньше кнопок нажимать.

maytonЭто называется Спираль Улама.
Глянул мельком, интересная метода, но получить все простые с ее помощью будет проблематично. Например посмотри где стоят 15 и 27.
Для криптографии подойдет. probabilistic algorithm
...
Рейтинг: 0 / 0
02.04.2015, 07:02
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924402
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercury60 скорее всего получено эмпирически
Это произведение первых простых чисел: 2*3*5 = 60 следующее такое 420.
Думаю на этом оптимизация как-то завязана.
...
Рейтинг: 0 / 0
02.04.2015, 07:22
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924408
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
kealon(Ruslan)Мужики,

мне кажется до определённого размера простые числа можно не хранить, достаточно перебора

999999937 / 50847534 =19.6

вот смотрите, при натуральном k

6k-1
6k - кратно 2 и 3
6k+1
6k+2 - кратно 2
6k+3 - кратно 3
6k+4 - кратно 2

т.е. все простые числа лежат в множестве 6k+/-1, достаточно проверять 1 из 3-х чисел
операции с регистрами гораздо быстрее чем попытки лезть в памятьМожно пойти дальше: остатки от деления на 30 для простых чисел больше 5 могут быть только 1,7,11,13,17,19,23,29. Можно сократить битовую карту почти вдвое - один байт на 30 чисел. Выкидываем кратные 7 - получаем 48 бит (6 байт) на 210 чисел. И т.д.
...
Рейтинг: 0 / 0
02.04.2015, 07:34
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924409
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima TSashaMercury60 скорее всего получено эмпирически
Это произведение первых простых чисел: 2*3*5 = 60 следующее такое 420.
Думаю на этом оптимизация как-то завязана.2*3*5 = 30
...
Рейтинг: 0 / 0
02.04.2015, 07:35
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924413
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Barlone2*3*5 = 30
вот я затупил
...
Рейтинг: 0 / 0
02.04.2015, 07:44
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924439
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Понял магичность числа 60.
 
Если взять все числа которые не делятся без остатка на 2,3,5, будет такая табличкаЧислоОт предыдущего7114132174192234296312376414432474492534596612676......

если табличку продолжить видно что повторы идут с частотой 60
Исследовал как бы в цикле шаги побольше делать.
Для выкидывания четных шаг 2. Т.е. перебор 50% значений
Для (2, 3) шаги 2,4,6. Перебор 25% (кол-во эл-тов/сумму)
Для (2, 3, 5) шаги 4,2,4,2,4,6,2,6,4,2,4,2,4,6,2,6. Перебор 26,7% (16/60) (отсюда и получилось 2*3*5 = 60)
Для (2, 3, 5, 7) Перебор 22,9% (96/420)

Неоптимальное число 60, лучше 420
...
Рейтинг: 0 / 0
02.04.2015, 08:32
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924442
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TГлянул мельком, интересная метода, но получить все простые с ее помощью будет проблематично. Например посмотри где стоят 15 и 27.
Для криптографии подойдет. probabilistic algorithm
С помощью нее и невозможно получить все простые. Но можно найти ряд полиномов внезапно (!) генерирующих
подмножество простых на интервале.
...
Рейтинг: 0 / 0
02.04.2015, 08:37
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924460
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Еще несколько магических чисел:
4620 для (2,3,5,7,11) Перебор 20,8% (960/4620)
60060 для (2,3,5,7,11,13) Перебор 19,2% (11520/60060)
1021020 для (2,3,5,7,11,13,17) это уже сложно в экселе обсчитать
Магическая формула простая: перемножаем все простые 2...N и еще раз на 2. Выкидываем кратные 2...N и строим ряд из разницы соседних. Цикл начинаем со следующего простого после N

В итоге перебор стремится к 5% (примерно столько простых в диапазоне), но как-то медленно стремится. Попробую для начала тройки выкинуть, уже двухкратное ускорение по сравнению с перебором нечетных.
...
Рейтинг: 0 / 0
02.04.2015, 09:04
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924474
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima T, еще раз на 2 то зачем умножать? http://primes.utm.edu/glossary/page.php?sort=WheelFactorization
...
Рейтинг: 0 / 0
02.04.2015, 09:14
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924479
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Large wheels are not particularly efficient. To remove 90% of the composites, we must use the primes up to 251. 95% requires the primes to 75,037. 96% requires the primes to 1,246,379. 97% requires the primes to 134,253,593!
...
Рейтинг: 0 / 0
02.04.2015, 09:15
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924507
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
BarloneDima T, еще раз на 2 то зачем умножать?
я исхожу из того чтобы циклом идти как можно большими шагами, там периодичность именно такая выходит
Например для (2,3) начинаем со следующего простого (5) и шагаем 2,4,6,2,4,6... т.е.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
int i = 5;
while(i < 10000) {
  i+=2;
  ... проверка i
  i+=4;
  ... проверка i
  i+=6;
  ... проверка i
}

Суммарный шаг 12(2+4+6) или (2*3)*2

для (2,3,5) шаги 4,2,4,2,4,6,2,6,4,2,4,2,4,6,2,6.
...
Рейтинг: 0 / 0
02.04.2015, 09:37
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924512
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima T, последовательность 4,2,4,2,4,6,2,6 повторяется дважды зачем?
...
Рейтинг: 0 / 0
02.04.2015, 09:41
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38924520
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
BarloneDima T, последовательность 4,2,4,2,4,6,2,6 повторяется дважды зачем?
Точно, задвоилась. В целом пофиг. На конечный процент пропусков не влияет.
...
Рейтинг: 0 / 0
02.04.2015, 09:49
| Ответить | Цитировать | Написать  
25 сообщений из 402, страница 5 из 17
  5  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]