Господа
мне надо сгенерировать совокупность простых чисел,
каждое число будет иметь размер в 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 number:DWORD
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, что это за алгоритм такой? Нельзя ли поподробнее? И с математическим обоснованием.
Что же касается полуразностей, то это не очень хорошая идея. Разности можно использовать исключительно в том случае, если нужен только последовательный перебор простых чисел. А в условии задачи об этом ничего не говорится. :)