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

Яж говорил. Primes - коварны. Кажущаяся простота первых результатов - воодушевляет. Но как
только - только ты выходишь на очередной уровень размеров (256-2048 бит) - начинают
"стрелять" различные технические ограничения. То компиллятор не умеет то железка не тянет
то хард диск мал.

Ну ладно. Это лирика.

Давайте порассуждаем. Есть Эратосфен. Это - серебрянная пуля. Он - стреляет. Он пока эффективнее
всяких индусов и прочих Шматкинов-Рабиновичей. Он - реально эффективнее моего pbfa - который
я постил лет 4 - 5 назад.

И мы реально умеем посчитать все primes за 8 сек до 4 млрд. Но что делать дальше?

Нам надо придумать алгоритм репликации всех вычёркиваний на следующее решето от 4 до 8 млрд.
на основании того что уже расчитано. Вопрос - как?
...
Рейтинг: 0 / 0
31.03.2015, 10:08
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38921981
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Марк, а мы разве разобрались с Аткином ? У нас пока только упрощенный алгоритм. Оригинальный алгоритм не реализован
...
Рейтинг: 0 / 0
31.03.2015, 10:16
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922018
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНам надо придумать алгоритм репликации всех вычёркиваний на следующее решето от 4 до 8 млрд.
на основании того что уже расчитано. Вопрос - как?
На самом деле просто, уже писал как (надо два решета 1...sqrt(X) и X...X+70 млн.), вопрос только как код оформить чтобы было универсально и пользоваться удобно.

Текущая реализация заточена на то чтобы быть готовой дать от 1 до X. Для больших Х не подходит.
Можно сделать поиск ближайшего больше Х, без кэширования результатов, но тогда несколько подряд медленно будут выбираться.
Можно запрашивать диапазон X1 ... X2, тогда как-то надо инициализировать этим диапазоном (верхняя граница нужна).

Классы не хочу, глобальных переменных тоже, а как при этом все красиво в одну функцию упихать не придумал. В идеале должно также остаться next_prime(X). Думаю пока
...
Рейтинг: 0 / 0
31.03.2015, 10:38
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922064
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryМарк, а мы разве разобрались с Аткином ? У нас пока только упрощенный алгоритм. Оригинальный алгоритм не реализован
Саш, займись. Даже если не взлетит, то хотя бы им проверим корректность Эратосфена. Для начала надо простейшую корректную реализацию, без оптимизаций, без биткарт (массив bool подойдет), главное чтобы работало, а дальше будем допиливать.
...
Рейтинг: 0 / 0
31.03.2015, 10:59
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922103
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryМарк, а мы разве разобрались с Аткином ? У нас пока только упрощенный алгоритм. Оригинальный алгоритм не реализован
Саш, займись. Даже если не взлетит, то хотя бы им проверим корректность Эратосфена. Для начала надо простейшую корректную реализацию, без оптимизаций, без биткарт (массив bool подойдет), главное чтобы работало, а дальше будем допиливать.

Через полтора часа начну :)
...
Рейтинг: 0 / 0
31.03.2015, 11:23
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922120
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryЧерез полтора часа начну :)
Главное без оптимизаций, чтобы читаемо было. Для начала достаточно чтобы до 1000 считал.

У меня вопрос по нему есть: нужны ли ему четные клетки решета? В реализации из википедии я не смог от них избавиться. Поэтому там биткарта в два раза больше места занимает.
...
Рейтинг: 0 / 0
31.03.2015, 11:33
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922180
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryМарк, а мы разве разобрались с Аткином ? У нас пока только упрощенный алгоритм. Оригинальный алгоритм не реализован
Если честно для меня оригнальный документ Prime sieves using binary quadratic forms
- A.O.L. Atkin , D.J.Bernstein - сложен для понимания. И я пока не знаю как его реализовать.
Wiki описывала понятно. Но если это не оригинальный - тогда я временно отложу своё мнение в
сторонку. Посмотрю какие будут у вас успехи с этим Шматкины-Бернштейном.

Ради интереса поискал сравнение.

http://stackoverflow.com/questions/5235865/comparison-of-sieve-of-sundaram-and-sieve-of-atkin-for-generating-a-list-of-prim In theory:

The sieve of Sundaram has an arithmetic complexity O(n log n).

The basic sieve of Eratosthenes has arithmetic complexity O(n log log n).

Optimized variants of the sieve of Eratosthenes have arithmetic complexity O(n).

The sieve of Atkin has not only arithmetic but also bit complexity O(n/log log n).

A magical sieve where you are given the primes, in order, takes time O(n/log n).

In practice, the sieve of Sundaram is so slow that no one uses it, and the
sieve of Atkin is slower than optimized Eratosthenes variants (although it's
at least competitive). Perhaps one day Atkin or something else will displace
Eratosthenes but it's not likely to happen soon. (Also, there's no such thing as magic.)



Последний абзац я пробую перевести. Вот что у меня вышло.
На практике, решето Сундарама настолько медленно, что никто его не использует, и
решето Аткина медленнее, чем оптимизированные варианты Эратосфена (хотя это
последнее спорно). Возможно, в один прекрасный день Аткин или какой-либ другой алгоритм будет вытеснять
Эратосфена, но это вряд ли произойдет в ближайшее время. Чудес не бывает.
...
Рейтинг: 0 / 0
31.03.2015, 12:01
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922256
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryЧерез полтора часа начну :)
Главное без оптимизаций, чтобы читаемо было. Для начала достаточно чтобы до 1000 считал.

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

судя по алгоритму нужны
...
Рейтинг: 0 / 0
31.03.2015, 12:37
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922342
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Начало пока такое

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#include <stdio.h>
#include <stdlib.h>

#define SIZE 1000 + 1 //d=[1;SIZE+1)
#define MAGIC_NUM 60

int divisors0_1[] = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58 };
int divisors0_2[] = { 3, 9, 15, 21, 27, 33, 39, 45, 51, 57 };
int divisors0_3[] = { 5, 25, 35, 55 };
int divisors1[] = { 1, 13, 17, 29, 37, 41, 49, 53 };
int divisors2[] = { 7, 19, 31, 43 };
int divisors3[] = { 11, 23, 47, 59 };

int element_belong(int x)
{
	for (int i = 0; i < sizeof(divisors1); ++i)	if (divisors1[i] == x) return 1;
	for (int i = 0; i < sizeof(divisors2); ++i)	if (divisors2[i] == x) return 2;
	for (int i = 0; i < sizeof(divisors3); ++i)	if (divisors3[i] == x) return 3;	
	return 0;
}
...
Рейтинг: 0 / 0
31.03.2015, 13:18
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922447
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
смысл примерно такой. Но я где-то ошибся, пока данный код работает неккоретно
 

Код: 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.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define SIZE 1000 + 1 //d=[1;SIZE+1)
#define MAGIC_NUM 60


int divisors0_1[] = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58 };
int divisors0_2[] = { 3, 9, 15, 21, 27, 33, 39, 45, 51, 57 };
int divisors0_3[] = { 5, 25, 35, 55 };
int divisors1[] = { 1, 13, 17, 29, 37, 41, 49, 53 };
int divisors2[] = { 7, 19, 31, 43 };
int divisors3[] = { 11, 23, 47, 59 };

int element_belong(int x)
{
	for (int i = 0; i < sizeof(divisors1); ++i)	if (divisors1[i] == x) return 1;
	for (int i = 0; i < sizeof(divisors2); ++i)	if (divisors2[i] == x) return 2;
	for (int i = 0; i < sizeof(divisors3); ++i)	if (divisors3[i] == x) return 3;	
	return 0;
}

int main()
{
	static bool* nums = (bool*)calloc(SIZE, sizeof(bool));//all numbers
	nums[2] = true;
	nums[3] = true;

	int n = 1;
	for (int x = 1;n<SIZE; ++x){
		for (int y = 1;; y += 2){
			n = 4 * x*x + y*y;
			if (n > SIZE)	
				break;
			if (element_belong(n%MAGIC_NUM) == 1)	
				nums[n] = !nums[n];
		}
	}

	n = 1;
	for (int x = 1; n<SIZE; x+=2){
		for (int y = 2;; y += 2){
			n = 3 * x*x + y*y;
			if (n > SIZE)
				break;
			if (element_belong(n%MAGIC_NUM) == 2)
				nums[n] = !nums[n];
		}
	}

	n = 1;
	for (int x = 2; n<SIZE; x ++){
		for (int y = 1;; y += 2){
			n = 3 * x*x - y*y;
			if (n > SIZE)
				break;
			if (element_belong(n%MAGIC_NUM) == 3)
				nums[n] = !nums[n];
		}
	}

	//output
	for (int i = 0; i < SIZE; ++i){
		if (nums[i])	printf("%i\n", i);
	}
	return 0;
}


...
Рейтинг: 0 / 0
31.03.2015, 13:58
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922481
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Прошу прощение, это не решает проблему, но всё же
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
int element_belong(int x)
{
	for (int i = 0; i < sizeof(divisors1)/sizeof(divisors1[0]); ++i)	if (divisors1[i] == x) return 1;
	for (int i = 0; i < sizeof(divisors2) / sizeof(divisors2[0]); ++i)	if (divisors2[i] == x) return 2;
	for (int i = 0; i < sizeof(divisors3) / sizeof(divisors3[0]); ++i)	if (divisors3[i] == x) return 3;
	return 0;
}
...
Рейтинг: 0 / 0
31.03.2015, 14:11
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922502
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Ребята, исправил практически. Ещё какая-то мелочь осталась

 
Код: 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.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define SIZE 1000 + 1 //d=[1;SIZE+1)
#define MAGIC_NUM 60

int sqrt_SIZE = (int)sqrt((float)SIZE);

int divisors0_1[] = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58 };
int divisors0_2[] = { 3, 9, 15, 21, 27, 33, 39, 45, 51, 57 };
int divisors0_3[] = { 5, 25, 35, 55 };
int divisors1[] = { 1, 13, 17, 29, 37, 41, 49, 53 };
int divisors2[] = { 7, 19, 31, 43 };
int divisors3[] = { 11, 23, 47, 59 };

int element_belong(int x)
{
	for (int i = 0; i < sizeof(divisors1) / sizeof(divisors1[0]); ++i)	if (divisors1[i] == x) return 1;
	for (int i = 0; i < sizeof(divisors2) / sizeof(divisors2[0]); ++i)	if (divisors2[i] == x) return 2;
	for (int i = 0; i < sizeof(divisors3) / sizeof(divisors3[0]); ++i)	if (divisors3[i] == x) return 3;
	return 0;
}

int main()
{
	static bool* nums = (bool*)calloc(SIZE, sizeof(bool));//all numbers
	nums[2] = true;
	nums[3] = true;

	int n = 1;
	for (int x = 1; x<sqrt_SIZE/4; ++x){
		for (int y = 1;; y += 2){
			n = 4 * x*x + y*y;
			if (n > SIZE)	
				break;
			if (element_belong(n%MAGIC_NUM) == 1)	
				nums[n] = !nums[n];
		}
	}

	n = 1;
	for (int x = 1; x<sqrt_SIZE/3; x+=2){
		for (int y = 2;; y += 2){
			n = 3 * x*x + y*y;
			if (n > SIZE)
				break;
			if (element_belong(n%MAGIC_NUM) == 2)
				nums[n] = !nums[n];
		}
	}

	n = 1;
	for (int x = 2; n<SIZE; x ++){
		for (int y = 1;y<x-1; y += 2){
			n = 3 * x*x - y*y;
			if (n > SIZE)
				break;
			if (element_belong(n%MAGIC_NUM) == 3)
				nums[n] = !nums[n];
		}
	}

	//output
	for (int i = 0; i < SIZE; ++i){
		if (nums[i])	printf("%i\n", i);
	}
	return 0;
}

...
Рейтинг: 0 / 0
31.03.2015, 14:22
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922572
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Сегодня уже не доделаю( Завтра утром постараюсь закончить
...
Рейтинг: 0 / 0
31.03.2015, 14:52
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922622
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Коллеги исходники в форуме это хорошо. Но может давайте постить
больше идеи и результаты? А для сорцов я создам SVN.
...
Рейтинг: 0 / 0
31.03.2015, 15:11
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922675
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Коллеги. Я вам щяс подкину концептуальный код. А вы подумайте... Взлетит не?

Не тестил. Интересует не компилляция а теоретическая полнота. Интересует перформанс
и возможные оптимизации. Интересует масштабирование и мета-компилляция.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
     long i=....;
     long counter2=1;
     long counter3=2;
     long counter5=5;
     long counter7=6;
     .......
     while(i){
     ...............
        if (counter2 && counter3 ..............................)
          printf("This number has interesting properties: %i\n",i);
     i++;     
     if (!--counter2) counter2=0;
     if (!--counter3) counter3=0;
     ............
     }



Прошу не придираться к возможным ошибкам. Это более идея чем реализация.
...
Рейтинг: 0 / 0
31.03.2015, 15:26
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922844
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonКоллеги. Я вам щяс подкину концептуальный код. А вы подумайте... Взлетит не?
Не понял это
Код: plaintext
1.
if (!--counter2) counter2=0;


раз код концептуальный, пиши без Сишной каши с вычислениями в условиях. Это тоже самое:
Код: plaintext
1.
2.
counter2--;
if (counter2 == 0) counter2 = 0;


Фигня какая-то.

А в целом, как понимаю, идея считать остаток от деления счетчиками. ИМХУ может взлететь.

maytonКоллеги исходники в форуме это хорошо. Но может давайте постить
больше идеи и результаты? А для сорцов я создам SVN.
+1 Саш, не замусоривай топик, прячь хотя бы под спойлер. А по хорошему кидай только готовое.
...
Рейтинг: 0 / 0
31.03.2015, 16:32
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922860
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я уберу чуть позже под спойлеры. Никто не против?
...
Рейтинг: 0 / 0
31.03.2015, 16:37
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922868
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Немного отвлеку вас. Нашёл страничку. Онлайн факторизатор.

http://ru.numberempire.com/numberfactorizer.php

Вот такое вот число
Код: plaintext
1.
999999999999999999999999999999999999999999999999999999999997


было разложено на множители менее чем за сек.
Код: plaintext
1.
719*757*6755603*271963805968702864258461551790513043662751795453



Вам интересно, как? Мне - да. Мне интересно.
...
Рейтинг: 0 / 0
31.03.2015, 16:40
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922878
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TФигня какая-то.

А в целом, как понимаю, идея считать остаток от деления счетчиками. ИМХУ может взлететь.

Я пытался эмулировать решето без самого решета. По сути конечным автоматом без состояния.
Моё решето делает лишние калькуляции от 2 до первого делителя впрочем это не должно
влиять на выхлоп. Здесь трудность - оценить насколько грузят CPU верчения круговых
счётчиков и сверка на не ноль с отсечениями.
...
Рейтинг: 0 / 0
31.03.2015, 16:43
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922898
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Поднял репку.

https://sourceforge.net/p/primegen/code/HEAD/tree/
...
Рейтинг: 0 / 0
31.03.2015, 16:50
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38922973
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonВам интересно, как? Мне - да. Мне интересно.
Надо возможности мат. библиотек поизучать, думаю там что-то такое задействовано. Типа GMP . Эта либа легко генерит простое число нужного размера, см. mpz_nextprime()

maytonЯ пытался эмулировать решето без самого решета. По сути конечным автоматом без состояния.
Теоретически сработает, вопрос как по производительности и памяти. Для каждого надо хранить: текущее состояние и до скольки считать. Можно потестить.
Назовем "Решето Майтона" :)


 
Нашел косяк в версии 2.0. Увлекся нечетными, забыл что еще четные бывают. next_prime(10) выдает 13 :(
это
Код: plaintext
1.
for(unsigned int i = (x | 1) + 2; i < limit; i += 2) {


заменить на это
Код: plaintext
1.
for(unsigned int i = ((x - 1) | 1) + 2; i < limit; i += 2) {


Позже выложу полную версию. Может еще чего найдется.
...
Рейтинг: 0 / 0
31.03.2015, 17:31
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38923083
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Хм....
Код: plaintext
1.
2.
3.
4.
5.
Function: void mpz_nextprime (mpz_t rop, const mpz_t op)

    Set rop to the next prime greater than op.

    This function uses a probabilistic algorithm to identify primes. For practical purposes it's adequate, the chance of a composite passing will be extremely small.



probabilistic algorithm - это вероятностный алгоритм. Это та шняга которая используется в криптографии
для поиска простых чисел для генерации ключа ЕМНИП.

У меня пока нет мнения по поводу probabilistic но это явно не та тема, которая мне интересна.
...
Рейтинг: 0 / 0
31.03.2015, 18:51
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38923099
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton probabilistic algorithm - это вероятностный алгоритм. Это та шняга которая используется в криптографии
для поиска простых чисел для генерации ключа ЕМНИП.
Для этих целей пользовал. Я для примера, глубоко туда не вникал, может там что еще есть полезное.
 
Решето Майтона не взлетело
Рабочий прототип алгоритма
Код: 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.
typedef struct {
	unsigned int val; // текущее значение
	unsigned int init; // начальное значение счетчика
} mcnt_t;

void mayton(int limit)
{
	mcnt_t cnt[100000];
	int total = 0; // общее кол-во счетчиков
	for(unsigned int i = 2; i < limit; i++) {
		bool is_prime = true;
		for(unsigned int j = 0; j < total; j++) {
			cnt[j].val--;
			if(cnt[j].val == 0) {
				cnt[j].val = cnt[j].init;
				is_prime = false;
			}
		}
		if(is_prime) {
			//printf("%d ", i);
			if(total >= sizeof(cnt) / sizeof(mcnt_t)) {
				printf("Need more counters :(\n");
				i = 100500999;
				break;
			}
			cnt[total].val = i;
			cnt[total].init = i;
			total++;
		}
	}
}


Результатtest 100000
atkin 10 msec
mayton 911 msec

можно подопиливать, но ИМХУ бесполезно
...
Рейтинг: 0 / 0
31.03.2015, 19:25
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38923122
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Интересно а какой "разрядности" этот ключик?



Попробуем посчитать.



Ну грубо говоря 200 бит.
...
Рейтинг: 0 / 0
31.03.2015, 19:57
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38923125
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну не взлетело так не взлетело. Я думал мета-компилляция спасёт моё решето...
...
Рейтинг: 0 / 0
31.03.2015, 20:02
| Ответить | Цитировать | Написать  
25 сообщений из 402, страница 2 из 17
  2  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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