Генератор простых чисел (до 10^9 за 5 сек) / C++

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)

25 сообщений из 402, страница 16 из 17

все

Генератор простых чисел (до 10^9 за 5 сек)

#39348603

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Затестил. На скорость оптимизация не влияет, те же 1.2 сек, разве что когда до 2^64 считать, то таблица перестанет в кэш проца влазить.

Исходник

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.

#define PRIME_TABLE 6541

uint32_t primes[PRIME_TABLE];
uint32_t primes2[PRIME_TABLE];
uint8_t primes_delta[PRIME_TABLE];

bool is_prime4(uint32_t n) {
	int prime = 3;
	int pos = 0;
	for (int i = 0; n >= prime * prime; i++) {
		if (n % primes[i] == 0) return false;
		prime += ((int) primes_delta[pos]) * 2;
		pos++;
	}
	return true;
}

// Инициализация таблиц
void init_primes() {
	int pos = 1;
	primes[0] = 3;
	primes2[0] = 9;
	for (int i = 5; i < 65536; i += 2) {
		if (is_prime2(i)) {
			primes[pos] = i;
			primes2[pos] = i*i;
			primes_delta[pos] = (uint8_t) ((i - primes[pos - 1]) / 2);
			pos++;
		}
	}
}

...

Рейтинг:

0 / 0

16.11.2016, 17:33

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39348607

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

VodoleYkaДА но тебе все равно нужен маркер какойто.. что число больше байта. вобщем и это детали
Оно всегда влазит. Я ж писал максимум разница 300 с небольшим нашлась.
У меня в коде эратосфена x64 проверка есть, она ни разу не сработала.

Код: plaintext

1.
2.
3.
4.

if(prime - p >= 512) {
	printf("Error cache: %llu - %llu = %llu > 512\n", prime, p, prime - p);
	return 0;
}

...

Рейтинг:

0 / 0

16.11.2016, 17:38

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39348614

VodoleYka

Гость

тю блин.. это я затупил.. вы в таблице уже поделенные значения хранить собирались.. согласен.

...

Рейтинг:

0 / 0

16.11.2016, 17:51

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39348709

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Dima TВ 4 раза ужимается.
Где-то в топике выше обсуждали. Одного байта достаточно до 2^64. Максимум разницу 300 с небольшим находил. Дополнительно еще на 2 делил, т.к. разница всегда четная. Так в 1 байт шаг до 512 влазит.

Таблица квадратов не нужна, с умножением время точно такое же

Код: plaintext

1.
2.
3.
4.
5.
6.
7.

bool is_prime3(uint32_t n) {
	int i;
	for (i = 0; n >= primes[i] * primes[i]; i++) {
		if (n % primes[i] == 0) return false;
	}
	return true;
}

я может чего не понимаю, а почему просто корень не извлечь сразу?

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

bool is_prime3(uint32_t n) {
	int i;
        int sqn = sqrt(n + 1);
	for (i = 0; sqn >= primes[i]; i++) {
		if (n % primes[i] == 0) return false;
	}
	return true;
}

вот тут есть приблизительные алгоритмы извлечения корня

...

Рейтинг:

0 / 0

16.11.2016, 22:25

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39348751

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T, давай актуализируем нашу песочницу.

Я кстати решил полностью уйти с SVN и поудалять всё с миграцией в github.

...

Рейтинг:

0 / 0

17.11.2016, 01:14

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39348778

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

kealon(Ruslan)я может чего не понимаю, а почему просто корень не извлечь сразу?
VodoleYka, не хотел с корнями связываться на асме. Затестил, по скорости одинаково что с корнями что с квадратами.

maytonDima T, давай актуализируем нашу песочницу.

Я кстати решил полностью уйти с SVN и поудалять всё с миграцией в github.
Там все актуально, больше доработок не было, переноси как есть.

...

Рейтинг:

0 / 0

17.11.2016, 07:12

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39348892

VodoleYka

Гость

Dima T,
ну FSQRT еще никто не отменял.. но там получается 2 операции с памятью. а это не гуд.. а вот регистровое умножение, вполне имеет право на жизнь..

...

Рейтинг:

0 / 0

17.11.2016, 11:18

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39348931

VodoleYka

Гость

Код: pascal

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.

function isPrime_asm(dwIn,Prime_tlb:DWord):DWord ;assembler;
asm
        mov ecx,eax //eax-dwIn  save for work
        mov esi,edx //edx-table prime numbers
@loop:
        lodsd       //load prime from tlb
        mov ebx,eax //data from Prime_tlb beckup

        xor edx,edx
        imul eax,eax
        test edx,edx //test resul>x32
        jnz  @prime

        cmp ecx,eax //dwIn<prime[i]^2
        jl @prime
//------------------
        //cmp eax, $FFFF    //ver 1.0 0:00:37 vs 0:00:03
        //ja @prime
//------------------
        //test eax,eax  //End of table
        //jz @prime

        //mov ebx,eax //data from Prime_tlb
        xor edx,edx
        mov eax,ecx//copy dwIn
        div ebx
        test edx,edx
        jz @not_prime
        nop
        jmp @loop
//-------------------
@not_prime:
        xor eax,eax
        jmp @exit
//-------------------
@prime:
        //mov [esi-4],ecx  //save prime
        mov eax,ecx
@exit:  //return 0-if not prime, or return prime
end;

ну короче както так.. ток теперь вызывающая процедура озабочена записью прайма в таблицу.

...

Рейтинг:

0 / 0

17.11.2016, 11:45

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39348933

VodoleYka

Гость

тю блин.. в коментах ошибка..
cmp ecx,eax //dwIn<prime[i]*prime[i]
ЗЫ
как же фигово что нельзя править сообщения

...

Рейтинг:

0 / 0

17.11.2016, 11:46

| Ответить | Цитировать | Написать

Период между сообщениями больше года.

Генератор простых чисел (до 10^9 за 5 сек)

#39601515

кибальчиш

Гость

Составил програмку расчёта первых простых чисел по методу Владимира Хренова.

http://www.zodiack.narod.ru/nchisla.pdf

Первые три миллиарда находит за 7 часов 10 минут. Хотелось бы ослышать оценку по скорости генерации по сравнению с решетом Эратосфена.
Протестировано на Intel Core I5-2400 3.1 Ghz, 4 Gb memory, Win 10 Pro.

29 cnt:10 end time: 08:03:18 date: 02/13/18
71 cnt:20 end time: 08:03:18 date: 02/13/18
113 cnt:30 end time: 08:03:18 date: 02/13/18
173 cnt:40 end time: 08:03:18 date: 02/13/18
229 cnt:50 end time: 08:03:18 date: 02/13/18
281 cnt:60 end time: 08:03:18 date: 02/13/18
349 cnt:70 end time: 08:03:18 date: 02/13/18
409 cnt:80 end time: 08:03:18 date: 02/13/18
463 cnt:90 end time: 08:03:18 date: 02/13/18
541 cnt:100 end time: 08:03:18 date: 02/13/18
1223 cnt:200 end time: 08:03:18 date: 02/13/18
1987 cnt:300 end time: 08:03:18 date: 02/13/18
2741 cnt:400 end time: 08:03:18 date: 02/13/18
3571 cnt:500 end time: 08:03:18 date: 02/13/18
4409 cnt:600 end time: 08:03:18 date: 02/13/18
5279 cnt:700 end time: 08:03:18 date: 02/13/18
6133 cnt:800 end time: 08:03:18 date: 02/13/18
6997 cnt:900 end time: 08:03:18 date: 02/13/18
7919 cnt:1000 end time: 08:03:18 date: 02/13/18
17389 cnt:2000 end time: 08:03:18 date: 02/13/18
27449 cnt:3000 end time: 08:03:18 date: 02/13/18
37813 cnt:4000 end time: 08:03:18 date: 02/13/18
48611 cnt:5000 end time: 08:03:18 date: 02/13/18
59359 cnt:6000 end time: 08:03:18 date: 02/13/18
70657 cnt:7000 end time: 08:03:18 date: 02/13/18
81799 cnt:8000 end time: 08:03:18 date: 02/13/18
93179 cnt:9000 end time: 08:03:18 date: 02/13/18
104729 cnt:10000 end time: 08:03:18 date: 02/13/18
224737 cnt:20000 end time: 08:03:18 date: 02/13/18
350377 cnt:30000 end time: 08:03:18 date: 02/13/18
479909 cnt:40000 end time: 08:03:18 date: 02/13/18
611953 cnt:50000 end time: 08:03:18 date: 02/13/18
746773 cnt:60000 end time: 08:03:18 date: 02/13/18
882377 cnt:70000 end time: 08:03:18 date: 02/13/18
1020379 cnt:80000 end time: 08:03:18 date: 02/13/18
1159523 cnt:90000 end time: 08:03:18 date: 02/13/18
1299709 cnt:100000 end time: 08:03:18 date: 02/13/18
2750159 cnt:200000 end time: 08:03:19 date: 02/13/18
4256233 cnt:300000 end time: 08:03:19 date: 02/13/18
5800079 cnt:400000 end time: 08:03:19 date: 02/13/18
7368787 cnt:500000 end time: 08:03:20 date: 02/13/18
8960453 cnt:600000 end time: 08:03:20 date: 02/13/18
10570841 cnt:700000 end time: 08:03:21 date: 02/13/18
12195257 cnt:800000 end time: 08:03:21 date: 02/13/18
13834103 cnt:900000 end time: 08:03:21 date: 02/13/18
15485863 cnt:1000000 end time: 08:03:22 date: 02/13/18
32452843 cnt:2000000 end time: 08:03:26 date: 02/13/18
49979687 cnt:3000000 end time: 08:03:30 date: 02/13/18
67867967 cnt:4000000 end time: 08:03:34 date: 02/13/18
86028121 cnt:5000000 end time: 08:03:39 date: 02/13/18
104395301 cnt:6000000 end time: 08:03:44 date: 02/13/18
122949823 cnt:7000000 end time: 08:03:49 date: 02/13/18
141650939 cnt:8000000 end time: 08:03:54 date: 02/13/18
160481183 cnt:9000000 end time: 08:03:59 date: 02/13/18
179424673 cnt:10000000 end time: 08:04:04 date: 02/13/18
373587883 cnt:20000000 end time: 08:04:58 date: 02/13/18
573259391 cnt:30000000 end time: 08:05:55 date: 02/13/18
776531401 cnt:40000000 end time: 08:06:55 date: 02/13/18
982451653 cnt:50000000 end time: 08:07:58 date: 02/13/18
1190494759 cnt:60000000 end time: 08:09:02 date: 02/13/18
1400305337 cnt:70000000 end time: 08:10:07 date: 02/13/18
1611623773 cnt:80000000 end time: 08:11:13 date: 02/13/18
1824261409 cnt:90000000 end time: 08:12:19 date: 02/13/18
2038074743 cnt:100000000 end time: 08:13:26 date: 02/13/18
4222234741 cnt:200000000 end time: 08:25:12 date: 02/13/18
6461335109 cnt:300000000 end time: 08:37:53 date: 02/13/18
8736028057 cnt:400000000 end time: 08:50:24 date: 02/13/18
11037271757 cnt:500000000 end time: 09:03:08 date: 02/13/18
13359555403 cnt:600000000 end time: 09:16:56 date: 02/13/18
15699342107 cnt:700000000 end time: 09:30:25 date: 02/13/18
18054236957 cnt:800000000 end time: 09:44:45 date: 02/13/18
20422213579 cnt:900000000 end time: 09:58:37 date: 02/13/18
22801763489 cnt:1000000000 end time: 10:12:29 date: 02/13/18
47055833459 cnt:2000000000 end time: 12:38:55 date: 02/13/18
71856445751 cnt:3000000000 end time: 15:14:08 date: 02/13/18

...

Рейтинг:

0 / 0

14.02.2018, 01:01

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39601519

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Без исходника как то незачотно. А вдруг ты пошутил?

...

Рейтинг:

0 / 0

14.02.2018, 01:58

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39601524

кибальчиш

Гость

mayton,
Пошутил в смысле слишком быстро или слишком медленно ? Какие тут шутки. Алгоритм в этой работе нарисован - смотри на картинку дерева чисел. Автор ничего не скрыл - всё на виду.
Принцип простой. Все простые числа или их произведения принадлежат двум последовательностям:

1) P1(i)=6*i-1, где i=1,2,....n (n стремится к бесконечности)
2) P2(i)=6*i+1, где i=1,...n

То есть:
P1(1)=6*1-1=5 - простое
P2(1)=6*1+1=7 - простое
P1(2)=6*2-1=11 - простое
P2(2)=6*2+1=13 - простое
P1(3)=6*3-1=17 - простое
P2(3)=6*3+1=19 - простое
P1(4)=6*4-1=23 - простое
P2(4)=6*4+1=25 - составное
P1(5)=6*5-1=29 - простое
P2(5)=6*5+1=31 - простое
...
Далее, каждое новое простое число генерирует две другие бесконечные последовательности. Так называемые "положительные" последовательности вида (m стремится к бесконечности)
K1(j) = P1(i)*P1(i)+P1(i)*6*j где j=0,1,2,....m
и "отрицаетльные" последовательности вида
K2(j)=P1(i)P2(i)+P1(i)*6*j где j=0,1,2,...m

Например:
Для i=1 и P1(соответствующее простое число 5 ):
"Положительная" последовательность
K1(P1(1),0)=5*5+5*6*0=25
K1(P1(1),1)=5*5+5*6*1=55
K1(P1(1),2)=5*5+5*6*2=85
...
"Отрицательная" последовательность
K2(P1(1),0)=5*7+5*6*0=35
K2(P1(1),1)=5*7+5*6*1=65
K2(P1(1),2)=5*7+5*6*2=95
...

Для i=2 и P2(соответствующее простое число 7 ):
"Положительная" последовательность
K1(P2(1),0)=7*7+7*6*0=49
K1(P2(1),1)=7*7+7*6*1=91
K1(P2(1),2)=7*7+7*6*2=133
...
"Отрицательная" последовательность
K2(P2(1),0)=7*11+7*6*0=77
K2(P2(1),1)=7*11+7*6*1=119
K2(P2(1),2)=7*11+7*6*2=161
...

Числа , которые учавствуют в "положительной" и "отрицательной" последовательностях вычёркиваются из последовательностей P1 и P2. Например, число 25 - первое число последовательности K1(P1(1),0), значит мы его вычёркиваем из ряда - число P2(4).
И так далее.

...

Рейтинг:

0 / 0

14.02.2018, 04:03

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39601525

кибальчиш

Гость

А вот и код. Прошу не пинать сильно - код сырой. Я его только вчера написал. Но в общем рабочий. :)

...

Рейтинг:

0 / 0

14.02.2018, 04:32

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39601558

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

кибальчишПервые три миллиарда находит за 7 часов 10 минут. Хотелось бы ослышать оценку по скорости генерации по сравнению с решетом Эратосфена.
В первом посте писал:
Dima Tасинхронный до 3 млрд. за 15 сек считает
Окончательный вариант быстрее в 3 раза.

Ссылки в первом посте на исходники умерли, залил на гитхаб.
next_prime32.h
next_prime64.h
Генератор простых чисел в заданном диапазоне

PS Модераторы поправьте ссылки в первом посте на эти

...

Рейтинг:

0 / 0

14.02.2018, 08:15

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39601593

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

В одном из prime-топиков у нас были контрольные таблицы с точным подсчетом
primes на интервалах целых чисел. Правда не могу вспомнить ссылку.

Надо-бы сравнить результат.

...

Рейтинг:

0 / 0

14.02.2018, 09:22

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39601603

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonВ одном из prime-топиков у нас были контрольные таблицы с точным подсчетом
primes на интервалах целых чисел. Правда не могу вспомнить ссылку.

Надо-бы сравнить результат.
У меня генератор считает количество в диапазоне.
Проверил выборочно, эти сходятся:
кибальчиш982451653 cnt:50000000
2038074743 cnt:100000000
11037271757 cnt:500000000
22801763489 cnt:1000000000
47055833459 cnt:2000000000
71856445751 cnt:3000000000

...

Рейтинг:

0 / 0

14.02.2018, 09:53

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39602433

кибальчиш

Гость

Dima T,
Спасибо. Ещё не мог бы ты сообщить время за которое твой генератор находит первые 3 миллиарда простых чисел ?
В общем, похоже что метод рабочий, перспективный, но в моей реализации на ассоциативном массиве не достаточно быстро пока получается. Если бы этот принцип переделать по аналогии с решетом на битовые операции - возможно он бы и решето с аткинами по скорости обогнал.
Да и возможности для распараллеливания здесь есть. Таблица считается один раз , а дальше запустить параллельные процессы на количество под-диапазонов равных количеству доступных процессоров . Должно дать линейное увеличение по скорости.
Как считаете ?

...

Рейтинг:

0 / 0

15.02.2018, 15:22

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39602508

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

кибальчишDima T,
Спасибо. Ещё не мог бы ты сообщить время за которое твой генератор находит первые 3 миллиарда простых чисел ?
В один поток 142 сек. Проц i7-6700K 4 ГГц

Код: plaintext

Count 3000000000 primes. Time: 142155 msec. Speed: 21103K/sec

Можешь сам скомпилировать, если позапускать есть желание, проект для MSVC . Могу собранный exe дать сюда если надо.

кибальчишВ общем, похоже что метод рабочий, перспективный, но в моей реализации на ассоциативном массиве не достаточно быстро пока получается. Если бы этот принцип переделать по аналогии с решетом на битовые операции - возможно он бы и решето с аткинами по скорости обогнал.
Поизучал твой алгоритм. По сути алгоритм похож на Эратосфена: имеем исходный набор потенциальных простых чисел и с помощью очередного простого числа вычеркиваем непростые.
ИМХО Эратосфен выглядит проще, т.е. операций меньше надо сделать. Сомневаюсь что обогнать его сможешь.

Главный тормоз у тебя в ассоциативном массиве. Я биткарту использовал вместо него.

кибальчишДа и возможности для распараллеливания здесь есть. Таблица считается один раз , а дальше запустить параллельные процессы на количество под-диапазонов равных количеству доступных процессоров . Должно дать линейное увеличение по скорости.
Как считаете ?
Эратосфен тоже хорошо параллелится. В четыре потока вчетверо быстрее.

Код: plaintext

Count 3000000000 primes. Time: 35602 msec. Speed: 84262K/sec

...

Рейтинг:

0 / 0

15.02.2018, 16:50

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39602588

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

кибальчишПринцип простой. Все простые числа или их произведения принадлежат двум последовательностям:

1) P1(i)=6*i-1, где i=1,2,....n (n стремится к бесконечности)
2) P2(i)=6*i+1, где i=1,...n
...
Далее, каждое новое простое число генерирует две другие бесконечные последовательности. Так называемые "положительные" последовательности вида (m стремится к бесконечности)
K1(j) = P1(i)*P1(i)+P1(i)*6*j где j=0,1,2,....m
и "отрицаетльные" последовательности вида
K2(j)=P1(i)P2(i)+P1(i)*6*j где j=0,1,2,...m
Долго вникал, но в итоге считаю что это форсированный Эратосфен. В отличии от оригинала тут пропускаются все числа кратные 2 и 3, за счет чего в идеале 6-тикратное ускорение, реально меньше, т.к. доп. операции появляются.

Перечитал свой код - он именно так и работает, пропускает кратные 2 и 3. Правда я своим путем до этого дошел, поэтому код получился слабочитаемым, если мягко сказать :)

...

Рейтинг:

0 / 0

15.02.2018, 18:20

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39602694

кибальчиш

Гость

Dima T,

Можно назвать этот метод "форсированным Эратосфеном".
Но по моему, это Эратосфен да не совсем.
Я набросал небольшой примерчик в Экселе поиска всех простых чисел до 102.
Посмотри. Группируем числа в группы по 6. Тогда искомые простые числа оказываются в колонках 1 и 5 - и так до бесконечности.
Далее - берём первое простое число 5. Оно образует две последовательности:
Отрицательную - 35, 65, 95, 125,... (жёлтенькая)
Положительную - 25,55,85,115,... (красненькая)
На основании этого - вычёркиваем из зелёных колонок 25,35,55,65,85,95 до конца нашего диапазона в 102.
Берём второе число - 7. Оно образует две последовательности:
Отрицательную - 77,119, 161, 203,... ( коричневая)
Положительную - 49,91, 133,175,... (синяя)
На основании этого - вычёркиваем из зелёных колонок 49,77,91

Итого после вычёркивания четырёх последовательностей остаются :
5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101 - все простые числа.

В общем получается, что весь диапазон до 100 задан всего двумя простыми числами 5 и 7.
Мы применили всего 9 вычёркиваний.
Теперь сравни с количеством вычёркиваний на анимации вот в этой статье на вики:

https://ru.wikipedia.org/wiki/Решето_Эратосфена

Главное что теперь понятен принцип формирования простых чисел.

...

Рейтинг:

0 / 0

16.02.2018, 05:27

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39602710

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

кибальчишМожно назвать этот метод "форсированным Эратосфеном".
Но по моему, это Эратосфен да не совсем.
Как уже написал - это Эратосфен с пропуском кратных 2 и 3. На вики видно что в оригинальном Эратосфене для вычеркивания использованы 2,3,5,7.

Посмотри последовательности для 5 и 7 в оригинальном Эратосфене:

Код: plaintext

25 30 35 40 45 50 55 60 65 70 75 80 85 90 95
49 56 63 70 77 84 91 98

Красным выделил те числа что ты использовал. Заметь, все что пропущено кратно 2 или 3.

...

Рейтинг:

0 / 0

16.02.2018, 07:39

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39603384

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Если решето считать кусками равными 2Гб (для удобства) то.
Количество бит (простых чисел) которые можно уложить в интервал равно 17 179 869 184.
Пока без учота четных и кратных тройкам.

На последнем чанке для целых диапазона int64, по формуле плотности вероятности
простых чисел на интервале от 9 223 372 019 674 906 623 до 9 223 372 036 854 775 807
мы получаем примерно 384 408 416 простых чисел. Соотношение primes к общему количеству
целых в чанке будет примерно 0.022.

Грубо говоря на каждые 50 бит целых чисел приходится 1 бит prime. Не очень рациональный
способ укладки данных. Кроме того итератор по данной биткарте будет иметь не очень
хороший КПД.

И хотя сомнительно что кто-то из нас досчитает до последних интервалов, все равно
тема расхода памяти меня интересует.

Какова должна быть структура данных чтобы обеспечить проверку на простоту (prime-test)
а также обеспечение интерфейса итерации.

...

Рейтинг:

0 / 0

17.02.2018, 00:58

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39603486

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonНа последнем чанке для целых диапазона int64 , по формуле плотности вероятности
простых чисел на интервале от 9 223 372 019 674 906 623 до 9 223 372 036 854 775 807
мы получаем примерно 384 408 416 простых чисел. Соотношение primes к общему количеству
целых в чанке будет примерно 0.022.

Грубо говоря на каждые 50 бит целых чисел приходится 1 бит prime. Не очень рациональный
способ укладки данных.
Уместить 64 бита в 50 уже компактно. Пропуск четных делается элементарно, поэтому считай не в 50, а 25.
25 бит на значение это очень хороший результат. Лучше чем массив.

Насчет итератора: если нужен последовательный доступ, то удобнее хранить разницу между соседними, тогда 1 байта достаточно на значение.

...

Рейтинг:

0 / 0

17.02.2018, 16:26

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39603548

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Да я помню наши эксперименты по хранению. В данной задаче меня интересовало два пункта.
- определение простоты числа
- факторизация большого числа
эти задачи связанны и постоянно перетекают из одной в другую. Задача генерации решета - решает
половину вопроса. Как оптимально хранить результат? Нужно-ли хранить? Как поддержать Iterable<Number>?

Прошло много лет. Я с тех пор периодически возвращаюсь к этой теме.

...

Рейтинг:

0 / 0

17.02.2018, 20:43

| Ответить | Цитировать | Написать

Генератор простых чисел (до 10^9 за 5 сек)

#39603585

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Вот как они так шустренько факторизируют? Здесь https://www.alpertron.com.ar/ECM.HTM

Вбил достаточно толстое число и получил разложение за доли секунды.

999999 139457 198374 509187 352837 465872 364875 628743 (48 digits) = 13 × 71 × 301153 × 740 107003 × 1 019694 655739 × 4 767010 128311 620141

Особенно последний множитель. Он - достаточно велик чтобы просто так его быстро разложить.

Рабин-Миллер? Нет. Он вроде только определяет факт простоты. И то с вероятностью.

...

Рейтинг:

0 / 0

18.02.2018, 00:39

| Ответить | Цитировать | Написать

25 сообщений из 402, страница 16 из 17

все

Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=57&msg=39601515&tid=2017971]:	0ms
get settings:	10ms
get forum list:	11ms
check forum access:	3ms
check topic access:	3ms
track hit:	180ms
get topic data:	8ms
get forum data:	2ms
get page messages:	52ms
get tp. blocked users:	1ms
others:	310ms

total:	580ms