генерация массива простых чисел

Господа

мне надо сгенерировать совокупность простых чисел,

каждое число будет иметь размер в 32 разряда. К примеру 1 это:

00000001h,2 это 00000002h и т.д. Буду, я это хранить в файле

asked.dat. Чтобы в будущем не мучиться и негенерировать боль-

шие простые числа.



передо мной несколько путей и только 2 известны мне:

1. Путь решета Эратосфена из Василенко, но мне не нравится, уж

больно много памяти надо!

2. Либо перебор, че нить вроде этого:



REPT 3

; так как 1,2,3 - простые числа

inc eax

mov dword ptr[esi],eax

add esi,4

ENDM



use:

inc eax,eax

jnc short exit_simple_number

push eax

call simple_number,eax

test eax,eax

jnz short next

pop eax

jmp use

next:

pop eax

mov dword ptr[esi],eax ; в esi ук.массива

add esi,4

jmp use



exit_simple_number:





simple_number proc numberWORD

pusha

mov eax,number

mov ebp,eax

round_s_n:

xor edx,edx

dec ebp

test ebp,0fffeh ; если 1, то выход

; ebp обнулиться не успеет

jz short exit_s_n

div ebp

test edx,edx

jz short exit_s_n

jmp round_s_n



loop round_s_n

dec esi



exit_s_n:

popa

ret

simple_number endp



Просьба указать мне на мои ошибки, как програмные так и на

логические, т.е. можно ли пойти по другому пути.

 

ИМХО проверить 32-х битное число на простоту быстрее всего перебором: нужно не более sqrt(2^32) = 2^16 делений чтобы точно определить, является ли число простым или нет и получить его полное разложение на множители.. я думаю, это не так ужи и долго для единовременных вычислений..

Другие варианты, безусловно, существуют, но в данной задаче я бы не стал их использовать..

 

flankerx



Ты плохо прочитал, мне не одно число надо, а совокупность простых чисел от 1h до ближайшего к 0ffffffffh причем все числа dword!

 

Примерно 1/10 натуральных чисел - простые. Если записывать простые числа как двойные слова, то потребуется около 1.6 ГБ. Можно вместо этого использовать битовый массив, представляющий все нечетные числа - тогда потребуется всего 256 МБ. Такая таблица вполне уместится в памяти современного десктопа, а значит можно будет использовать метод Эратосфена.

Можно еще проверять делимость числа на все ПРОСТЫЕ числа, не превышающие квадратный корень тестируемого. Тогда потребуется не более 6542 делений на одно число.

Sapienti sat.

 

Есть такая функция pi(x) - для любого натурального x она выдает ПРИМЕРНОЕ количество простых чисел не превышающих x,

при больших х она стремится к, если не ошибаюсь, x/ln(x)

(днем точно скажу),

это так... для оценки

А вообще оптимальный алгоритм на мой взгляд следующий:

1) числа 2 3 заносим в наш массив

2) прибавляем к предыдущему числу 2

3) проверяем делимость текущего числа на уже заполненные элементы массива, пока эти элементы не превышают sqrt() от нашего кандидата

4) если он ни делитя ни на одно из этих чисел,

добавляем его в массив и переходим к шагу 2

5) переходим к шагу 2, если еще не все числа перебрали



ЗЫ проверять делимость на 2 вовсе не обязательно, ведь мы потом берем только нечетные числа...

 

Вот тут подумалось...



Алгоритм "эратосфеново решето" вычеркивает из таблицы из N чисел все числа общего вида (т. е. не простые). Всякое такое число имеет простые делители, из которых хотя бы один лежит в диапазоне [2..sqrt(N)]. Следовательно, если вычеркнуть все числа, кратные простым числам из диапазона [2..int(sqrt(N))], то все оставшиеся числа будут простыми.



Если N = 2^32-1, то достаточно вычеркнуть числа, кратные [2..65521] (65521 - максимальное простое число, меньшее 65536). Количество этих "контрольных" чисел невелико (6542). Вырисовывается такая идея:



1) разбиваем всю таблицу чисел на блоки, умещающиеся в памяти;

2) создаем таблицу из 6542 элементов, в которую записываем "контрольные" простые числа < 65536 и текущие числа, кратные "контрольным";

3) для каждого "контрольного" числа выполняем цикл, вычеркивающий в текущем блоке все "кратные" числа; сохраняем в массиве очередное "кратное" число, находящееся в следующем блоке;

4) когда все "контрольные" числа обработаны, сбрасываем текущий блок на диск, генерируем следующий блок и переходим к пункту 3), и так пока не обработаем все 4G чисел.



Немного сумбурно. Постараюсь к вечеру написать программу (Object Pascal с ассемблерными вставками устроит ?

 

\masm32\EXAMPL10\CONSOLE\HASHAPP\PRIMES\

Лежит одноименный файлик с исходником выдает текстовый файл простых чисел от 0 до 65535. Вот от него и пляши.

 

Выкладываю, что получилось.

Программа на Object Pascal (для простоты), но все вычисления на ассемблере. Пишет в файл битовый массив блоками по 4 МБ.

Вроде бы, все работает правильно, только медленно.

1575220741__Eratos4G.zip

 

обязательно гляну!

 

Я делал так:

1. Решетом Эратосфена находишь все простые числа, не превышающие 65536

2. Выбераешь первые несколько чисел и перемножаешь. Например, возьмём 2, 3 и 5. Перемножаешь их и получаешь 30. После этого из диапазона 0..29 вычёркиваешь все числа, делящиеся на 2, 3 или 5. Получаешь числа

1, 7, 11, 13, 17, 19, 23, 29 (в данном случае все получились простые, но так будет не всегда). Тогда нужно проверять на делимость лишь числа вида

30k+1

30k+7

30k+11

30k+13

30k+17

30k+19

30k+23

30k+29

т. е. изначально

x=65537 (первое чило, большее 65536 нашего вида, 65536=30k+17)

проверить x на делимость на простые числа, не превышающие sqrt(x). если не делится, запомнить x

x+=(19-17)

повторить проверку

x+=(23-19)

....

и так далее, пока x<=0FFFFFFFFh

3. Записывать в файл можно полуразность простых чисел, запихивая её в один байт

 

Loger



Спасибо на добром слове!

 

Вот что братья индусы напридумали в 2002 году ttp://www.cse.iitk.ac.in/news/primality.pdf

В частности, вырезка оттуда

http://nelidovo2.narod.ru/simple.png

 

ovod



Причем здесь это? Повыпендриваться описанием алгоритмов захотелось?

 

Не стал мудрить и искать оригинальных решений, просто сделал перебор, подобный тому что описал в начале топа. Токо, есно, улучшил! Говорят, друзья, что методом алгоритма Эвклида, как то можно простые числа генерить. Но я плохой математик и не вижу КАК? Даже не смотря на темы форума, к примеру поднятую Володей. Ну, чтож. Буду перебирать

 

Loger, что это за алгоритм такой? Нельзя ли поподробнее? И с математическим обоснованием.

Что же касается полуразностей, то это не очень хорошая идея. Разности можно использовать исключительно в том случае, если нужен только последовательный перебор простых чисел. А в условии задачи об этом ничего не говорится.

 

Есть и другой алгоритм. Называется "алгоритм колеса". В книгу пойдет. EvilsInterrupt, если тебе совсем не в терпеж, дам наброски в конце недели. Если может подождать - жди и ты.

 

ava:

алгоритм мой

математическое обоснование писать не буду, но нетрудно доказать, что что числа вида (30k+n), где n не пренадлежит {1,7,11,13,17,19,23,29} не являются простыми (они делятся на 2, 3 или 5). А остальные числа мы проверяем на простоту делением.

если нужен произвольный доступ к простым числам, скорость доступа можно увеличить, записывая каждое n-нное число полностью. например, если писать каждое 29-е число полностью то получится

struct primes_block{

unsigned long first;

unsigned char primes[28];

}

учитывая, что данные в кэш грузятся по 32 байта, при правильном выравнивании массива таких блоков, потери производительности почти не будет

 

Loger, я вот тут подумал над твоим алгоритмом и наконец-то понял, что это действительно очевидно



"Интра-фреймы" по-своему решают проблему поиска чисел, но одновременно увеличивают размер файла, так что основное преимущество использования полуразностей - компактность (по сравнению с полной записью) - уменьшается. К тому же следует иметь в виду, что полуразность может оказаться больше 256. В данном случае все в порядке - максимальная полуразность равна 168 - но это выяснилось только после создания таблицы. >

 

All



Дружно пошлем все володины проблемы на ..., что бы он быстрее труд на бацал!

 

Я так понимаю что массив простых чисел нужен для проверки большого числа на простоту ?



Я в свое время так сделал массив занял 800+ мег.



После чего он оказался ненужен так как есть как минимум 2 способа проверки числа на простоту (читай Кнута).



PS: Может я не понял для чего все это нужно , так что сильо не пинайте