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

Если ты - счастливый обладатель Пингвина - то запускай

Код: plaintext
1.
$ ./pbfa 1000000000 > /dev/null



Для винды.
Код: plaintext
1.
$ pbfa.exe 1000000000 > NUL



или в файл. А так будет ацкий тормоз.

Но вобщем-то смысл моей работы был в том что числа нужно где-то хранить. Просто count(*) мне неинтересен.
...
Рейтинг: 0 / 0
02.04.2015, 21:21
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925678
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
В debug запустил потому что MS VC его по дефолту ставит. Сейчас вообще в дебаг не компилируется. Мелочи.

Сегодняшние изучения. Микрооптимизация ускоряющая твой код на 20-25%
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
	primesCache.push_back(3);
...
	int min_prime = 5;
...
	int step = 4;
	for (int c1 = 5; c1 < max_prime; c1 += step) {
		step = 6 - step;
...


Это пропуск кратных тройке.

Там счетчик итого показывает на 1 больше, но вроде это со счетчиком проблема.
...
Рейтинг: 0 / 0
02.04.2015, 21:50
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925690
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton, Dima T

Добавьте простенький CMakeLists
хотя бы как во вложении (он для pbfa)
...
Рейтинг: 0 / 0
02.04.2015, 22:12
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925691
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНо вобщем-то смысл моей работы был в том что числа нужно где-то хранить. Просто count(*) мне неинтересен.
 
Допили под свои потребности
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#include "next_prime.h" 

int main(int argc, char* argv[])
{
	uint32_t min = 0, max = 0;
	if (argc == 3) {
		min = atoi(argv[1]);
		max = atoi(argv[2]);
	}
	if(max <= min) {
		printf("Usage:\nprimestore min max\n");
	} else {
		uint32_t x = next_prime(min);
		while(x < max) {
			printf("%u\n", x);
			x = next_prime(x);
		}
	}
	any_key();
}


пока x32 позже будет next_prime64()
...
Рейтинг: 0 / 0
02.04.2015, 22:13
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925695
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Рационально. Потестил.

На 100_000 сошлось. Значит всё будет ок. Выражение step переделал. Скорость еще не мерял но с шагом больше
двух полюбому быстрее будет.

Код: plaintext
1.
2.
	for (int c1 = min_prime; c1 < max_prime; c1 += step) {
		step^=0x0006;


Fixed.
Код: plaintext
1.
2.
3.
4.
5.
6.
Revision: 15
Author: mayton
Date: Thursday, April 02, 2015 10:17:16 PM
Message:
Improovement speed of main loop. Added non linear step.
----
...
Рейтинг: 0 / 0
02.04.2015, 22:19
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925705
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton, похоже ты не понимашь главного: next_prime(X) это простейший супер-интерфейс получения простых чисел. Хочешь с нуля считай, хочешь - любое следующее, как следствие - диапазон от .. до, хочешь на простоту проверяй Х == next_prime(X - 1). Разве что предыдущее сложно получить.

а дальше сам решай сохранять их или просто считать сколько получилось.

PS mayton, готовь диски, x64 простых ~4*10^17, или 400`000 терачисел :)
...
Рейтинг: 0 / 0
02.04.2015, 22:31
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925713
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, какие ограничения на память будут действовать для твоего решета x64 ?
...
Рейтинг: 0 / 0
02.04.2015, 22:41
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925714
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonСкорость еще не мерял но с шагом больше двух полюбому быстрее будет.
Это тест был незаконченный, хочу унивесальный пропуск сделать (2,3,5,7 ...) Затестить какой оптимальнее.

По замерам времени: возьми мой header.h, там есть now_msec() для замеров в мс, а то в секундах несерьезно. Можешь стандартный clock() использовать, только в линуксе он считает сколько програма реально проработала, всякие sleep() не учитывает, но в данном случае это не критично.
...
Рейтинг: 0 / 0
02.04.2015, 22:41
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925717
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima T, какие ограничения на память будут действовать для твоего решета x64 ?
Можно медленно с 64Кб, можно быстро с максимум 750 Мб(все простые x32 в uint32). Оба варианта дадут одинаково быстро посчитают однократно next_prime64(X), разница в скорости будет на расчете диапазона (при малом кэше придется пересчитывать). Для быстрого расчета next_prime64(X) надо в кэше иметь все простые до sqrt(X), в первый заход они расчитываются.
...
Рейтинг: 0 / 0
02.04.2015, 22:50
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925726
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну... перефразирую вопрос. Вот задача. Проверить на простоту это число.

Код: plaintext
1.
271963805968702864258461551790513043662751795453


Факторизовать. Как более общая постанока. Разложить на простые.

Я писал об этом в начале топика. Меня увлекает это. Я - have fun от подобных
головоломок.
...
Рейтинг: 0 / 0
02.04.2015, 23:04
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925787
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
maytonПросто мы решаем разные задачи.

Я искал оптимальные способы хранения расчитанных primes на диске
чтобы факоризировать сверх-длинные целые.

maytonНу... перефразирую вопрос. Вот задача. Проверить на простоту это число.

Код: plaintext
1.
271963805968702864258461551790513043662751795453


Факторизовать. Как более общая постанока. Разложить на простые.

Я писал об этом в начале топика. Меня увлекает это. Я - have fun от подобных
головоломок.Чтобы "факоризировать сверх-длинные целые", не надо хранить простые числа. Бесполезно это.

А число ваше простое, по крайней пере по вероятностным тестам. Нужно доказанное простое - смотрите на что-нибудь типа https://ru.wikipedia.org/wiki/Тест_Миллера_(теория_чисел) или https://ru.wikipedia.org/wiki/Критерий_Поклингтона
...
Рейтинг: 0 / 0
03.04.2015, 05:27
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925799
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonУ меня был план - хранить расчитанные primes в бинарных файлах специально оптимизированных по размеру (каждое число укладывалось в несколько бит).
Делись планом. Это одна из недорешанных проблем.
Из моего алгоритма Эратосфен никуда не не исчез, поэтому кэш нужен. Причем нужен быстрый последовательный перебор от 2 до N. Где N макс.простое до 2^32
Самое быстрое это вектор uint32, для расчета любого x64 под него потребуется 750 Мб. Пока использована биткарта, ей хватает 256 Мб, но чтение из нее это побитовый перебор - очень не быстро, секунда на проход. Есть мысль хранить расстояние между соседними, если не окажется дырок больше 128К, то можно будет взять массив uint16 - это 375 Мб
...
Рейтинг: 0 / 0
03.04.2015, 06:56
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925813
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
mayton271963805968702864258461551790513043662751795453


Критерий Поклингтона для вашего числа:
N = 271963805968702864258461551790513043662751795453
N-1 = 90233392513315464829662320219386916428363 * 3014004
Берем a=2, проверяем что 2^(N-1) mod N = 1 и gcd(2^3014004-1, N) = 1 - это легко, возьмите gmp (или mpir под windows) и проверьте. Я проверил.
Правда теперь надо еще доказать, что 90233392513315464829662320219386916428363 простое.
Для него можно проделать все то же самое, теперь упремся в доказательство простоты 10378812113332811689632196942648598623.
С этим хуже, для него N-1 = 2*3*11*73*761*83537*403253*1108092371*75833962769 - тут нет простого множителя больше квадратного корня, критерий Поклингтона не получиться использовать.
...
Рейтинг: 0 / 0
03.04.2015, 07:41
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925818
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНу... перефразирую вопрос. Вот задача. Проверить на простоту это число.

Код: plaintext
1.
271963805968702864258461551790513043662751795453


Факторизовать. Как более общая постанока. Разложить на простые.

Я писал об этом в начале топика. Меня увлекает это. Я - have fun от подобных
головоломок.

Есть библиотеки специальные, GMP например. Результат совместного творчества решения подобных головоломок умными дядьками. ИМХУ мне их точно не перегнать.
 
271963805968702864258461551790513043662751795453 is probably prime
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
#include <gmp.h>

int main()
{
	mpz_t x;
	mpz_init_set_str(x,"271963805968702864258461551790513043662751795453",10);
	switch(mpz_probab_prime_p(x, 1)) {
		case 2:
			gmp_printf("%Zd is definitely prime\n", x);
			break;
		case 1:
			gmp_printf("%Zd is probably prime\n", x);
			break;
		case 0:
			gmp_printf("%Zd is definitely composite\n", x);
			break;
		default:
			printf("error\n");
	}
	mpz_clear(x);
}


не понял что второй параметр mpz_probab_prime_p() задает
https://gmplib.org/manual/Number-Theoretic-Functions.html

Я так понимаю нет чудо теста который гарантированно скажет что это простое число, 100% гарантия это только перебор с делениями на все sqrt(x) и производные от него. Вобщем все упирается в sqrt(x), в данном случае до 10^24 или перебор ~10^22 простых. Со скоростью 1 млрд. в секунду уйдет всего 317 млрд. лет :)
...
Рейтинг: 0 / 0
03.04.2015, 07:55
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925819
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
BarloneЧтобы "факоризировать сверх-длинные целые", не надо хранить простые числа. Бесполезно это.

А число ваше простое, по крайней пере по вероятностным тестам. Нужно доказанное простое - смотрите на что-нибудь типа https://ru.wikipedia.org/wiki/Тест_Миллера_(теория_чисел) или https://ru.wikipedia.org/wiki/Критерий_Поклингтона
Я вобщем-то ждал этого. Ну что-ж спасибо за совет.
Думаю что в обучательных целях некоторое хранилище
простых кому-то пригодиться.
...
Рейтинг: 0 / 0
03.04.2015, 08:02
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925821
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДумаю что в обучательных целях некоторое хранилище простых кому-то пригодиться.
возможно пригодится 17467271
...
Рейтинг: 0 / 0
03.04.2015, 08:08
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925825
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TЯ так понимаю нет чудо теста который гарантированно скажет что это простое число, 100% гарантия это только перебор с делениями на все sqrt(x) и производные от него. Вобщем все упирается в sqrt(x), в данном случае до 10^24 или перебор ~10^22 простых. Со скоростью 1 млрд. в секунду уйдет всего 317 млрд. лет :)
Дима! Ну что за пессимизм. А векторность. Мультипоточность. Гриды.

Ну прямо сел на пенёк и упал духом!

Go! Go! Секс. Rock-n-Roll и С++!!
...
Рейтинг: 0 / 0
03.04.2015, 08:12
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925829
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДима! Ну что за пессимизм. А векторность. Мультипоточность. Гриды.
Не, это число конечно обсчитаем всей планетой за пару месяцев, а второе где считать будем?

Как ни крути - надо ускорять Эратосфена алгоритмическими способами.
...
Рейтинг: 0 / 0
03.04.2015, 08:17
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925887
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima TЯ так понимаю нет чудо теста который гарантированно скажет что это простое числоНу как же нет, надо провести тест Миллера для всех простых не превосходящих 2*log²(N) - примерно до 23858. А, ну еще гипотезу Римана доказать :)
...
Рейтинг: 0 / 0
03.04.2015, 09:35
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925928
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima TЕсть мысль хранить расстояние между соседними, если не окажется дырок больше 128К, то можно будет взять массив uint16 - это 375 МбВроде бы отсутствие контрпримеров к гипотезе Лежандра гарантирует отсутствие дырок больше 128К для простых не превосходящих 2^32. Или нет?
...
Рейтинг: 0 / 0
03.04.2015, 10:12
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925940
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Зафиксировал next_prime64(). Теперь она x64.
Код: plaintext
1.
prime 1000000000000037 time 220 msec




Barlone А, ну еще гипотезу Римана доказать :)
Как понимаю из-за этой "мелочи" GMP пишет is probably prime :)
Код: plaintext
1.
1000000000000037 is probably prime
...
Рейтинг: 0 / 0
03.04.2015, 10:19
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925971
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
BarloneDima TЕсть мысль хранить расстояние между соседними, если не окажется дырок больше 128К, то можно будет взять массив uint16 - это 375 МбВроде бы отсутствие контрпримеров к гипотезе Лежандра гарантирует отсутствие дырок больше 128К для простых не превосходящих 2^32. Или нет?
Посчитать элементарно
 
max delta 336 between 3842610773 and 3842611109
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
		uint32_t t = now_msec();
		uint32_t cnt = 0;
		uint32_t delta = 0;
		uint32_t x = 1;
		while(x && x < TEST) {
			cnt++;
			uint32_t xn = next_prime(x);
			if(xn - x > delta) {
				delta = xn - x;
				printf("max delta %u between %u and %u\n", delta, x, xn);
			}
			x = xn;
		}
		printf("end calc to %u count %u time %u msec\n", TEST, cnt, now_msec() - t);


Результатmax delta 6 between 23 and 29
max delta 8 between 89 and 97
max delta 14 between 113 and 127
max delta 18 between 523 and 541
max delta 20 between 887 and 907
max delta 22 between 1129 and 1151
max delta 34 between 1327 and 1361
max delta 36 between 9551 and 9587
max delta 44 between 15683 and 15727
max delta 52 between 19609 and 19661
max delta 72 between 31397 and 31469
max delta 86 between 155921 and 156007
max delta 96 between 360653 and 360749
max delta 112 between 370261 and 370373
max delta 114 between 492113 and 492227
max delta 118 between 1349533 and 1349651
max delta 132 between 1357201 and 1357333
max delta 148 between 2010733 and 2010881
max delta 154 between 4652353 and 4652507
max delta 180 between 17051707 and 17051887
max delta 210 between 20831323 and 20831533
max delta 220 between 47326693 and 47326913
max delta 222 between 122164747 and 122164969
max delta 234 between 189695659 and 189695893
max delta 248 between 191912783 and 191913031
max delta 250 between 387096133 and 387096383
max delta 282 between 436273009 and 436273291
max delta 288 between 1294268491 and 1294268779
max delta 292 between 1453168141 and 1453168433
max delta 320 between 2300942549 and 2300942869
max delta 336 between 3842610773 and 3842611109
end calc to 4294967295 count 203231690 time 23904 msec

Замечательно. Хватит одного байта. Все разницы четные, поэтому на 2 поделим. Т.е. итого 203 Мб.
31 вариант всего, можно в 5 бит уместить. Т.е. 127 Мб.
...
Рейтинг: 0 / 0
03.04.2015, 10:41
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926009
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dima T31 вариант всего, можно в 5 бит уместить. Т.е. 127 Мб.
Обсчитался, немного, не все скопировал с консоли. Еще есть разницы 2 и 4, т.е. вариантов 33, поэтому 6 бит надо. Или 152 Мб.
Это если кто хранением захочет заняться.

Мне больше однобайтовый вариант подходит, хранить delta/2, чтобы быстро писать и быстро читать.
...
Рейтинг: 0 / 0
03.04.2015, 10:59
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926015
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima T31 вариант всего, можно в 5 бит уместить. Т.е. 127 Мб.Не, про 31 вариант неправда. Точно есть разности 2 и 4. Ну и после нахождения большой дельты вы уже не показываете меньшие.
...
Рейтинг: 0 / 0
03.04.2015, 11:02
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926022
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Например, между 139 и 149 дельта 10.
...
Рейтинг: 0 / 0
03.04.2015, 11:06
| Ответить | Цитировать | Написать  
25 сообщений из 402, страница 8 из 17
  8  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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