program Ishem_prostie_chisla_v_sotne;
uses crt;
var
   a,b : array [1..100] of byte;
   p     : byte;
   i,n,z : byte;
label
   l,l2;
begin
ClrScr;
a[1]:=3;
b[1]:=3;
i:=3;
n:=0;
l: p:=0;
  for z := 1 to n do  begin
  b[z]:=b[z]-1;
  if b[z] = 0 then begin
                    b[z]:=a[z];
                    p := 1;
                    {goto l2;}
                   end;

  end;
if p<>1 then begin
    n:=n+1;
    a[n]:=i;
    b[n]:=i;
write(a[n],' ');
end;
l2: i:=i + 2;
{write(i,' ');}
if i<=100 then goto l;
{for i := 1 to 24 do begin
write(a[i],' ');
end;}
write(n);
end.

Я долго коптил, и нашёл закономерность "размножения" простых чисел. (кто не верит пусть компилит!!!!)
Я прошу помощи перевода етого кода на асм, при этом надо сделать возможность бесконечного увеличения массива. заранее сенкс

И чем конкретно этот метод новый?

Я  вообще особо не рублю на Дельфи/Паскале, но... вообще на кой чёрт тебе искать эти числа? ведь можно просто брать число, проверять простое оно или нет, потом, если оно простое кидать его в файл или куда надо. на С++ что то в роде:

int num_to_check = 1000;
for(int a = 0; a<num_to_check; a++)
 if(Prostoje4islo(a)==TRUE) printf("%i\n", a);

Ф-ция Prostoje4islo проверяет простое ли число и, если да, то printf выводит это число на экран. Не верю, что на Паскали/Дельфи так нельзя сделать.

2 Kefir - можно конечно, но проблема с простыми числами остаётся весьма острой, код автора тоже не поможет. Например видоизменим задачу - надо найти все простые числа в интервале от 10^20 до 10^22... Желательно за разумный интервал времени...

"Я долго коптил, и нашёл закономерность "размножения" простых чисел. "
Смелое утверждение :-). Если ты действительно сформулировал закон распределения простых чисел, тогда тебе нужно премию, как минимум, Филдса выдать. Кстати, кажется на Vingrade в каком-то разделе форума кто-то статью выдал, что какие-то ученые составили алгоритм получения простого числа, но чего-то я больше нигде подобной информации не читал. Для тех кто не в курсе (мало ли как бывает) простые числа - число которые деляться только на 1 и на себя (1,2,3,5,7,11,13,17 и т.д. (только вот как так? :-) ) ).

2 Vit:
Это примерно 99 в 20й итераций... нда... хорошего времени не получается, но быстродействие компьютеров постоянно растёт, так что очень возможно, что вскоре и такой способ подойдёт.
Вообще я не имел в виду таких астрономических чисел, просто при довольно нечасто надо находить все простые в этом интервале.
2 Dapo:
Может ты это имел в виду:
http://www.cse.iitk.ac.in/primality.pdf
?
Это алгоритм дающий 100% уверенность в простоте числа (или же в том что оно не простое).

Дело в том, что над этой проблемой "покоптили" еще в древности. В результате появился метод с названием "решето Эратосфена", который довольно часто изучается в школе...
если интересно - сходите, например, на www.nature.ru и наберите в поиске "решето Эратосфена"

2 maxim1000:
Решето - это конечно хорошо, но и ты тоже не поленись, зайди по ссылке в моём предидущем мсг. Тоже довольно интересно.

Тема перемещена в раздел алгоритмов

А как же Кнут с его алгоритмами.....

Поиск простых чисел практически нужен например в криптоанализе системы шифрования с открытым ключом (например RSA). По крайней мере очень сильно убыстрит его.

Ну вот, народ, ловите. Кто тут говорил, что статью хотел:
http://www.cse.iitk.ac.in/news/primality.pdf

Сделай exe и дизасемблируй его ))) Вот тебе и код в АСМ

а так нормально! но лучше в динамической памяти Так как на большие массивы места не хватит)

Выведена формула получения простых чисел
http://www.laplas.narod.ru/moiform.htm

пункт №4



где k целое число от 1 до бесконечности. Выражение в скобках ограниченных снизу обозначает целую часть дроби k/6, либо само значение этой дроби если k кратно 6, ну а функция n=[(k-1)mod(6)] и n=[(k)mod(6)] вам я надеюсь знакома - сравнимость чисел n и k-1, k по модулю 6.
Эта формула даёт все простые числа по порядку начиная с 5. Так же по этой формуле получаются составные числа. Общая доля отсева равна 11/15=0.73333(3).

Цитата(maxim1000 @ 11.1.2003, 00:05)

если интересно - сходите, например, на www.nature.ru и наберите в поиске "решето Эратосфена"

Или посмотритет тут:
http://forum.vingrad.ru/index.php?showtopic=30076

Может я не вьехал во что-то, но вот фразу:

Цитата

Эта формула даёт все простые числа по порядку начиная с 5. Так же по этой формуле получаются составные числа. Общая доля отсева равна 11/15=0.73333(3).

я не совсем понял... А чем эта формула отличается по смыслу от известной 2^n - 1, там вроде тоже простые получаются числа и составные иногда проскакивают...

Цитата(Dapo @ 10.1.2003, 17:21)

"Я долго коптил, и нашёл закономерность "размножения" простых чисел. "

Есть формула асимптотического распределения простых чисел: p(x) = x/ln x
показывающая, сколько простых числе содержится на интервале 1..x.

Цитата

Общая доля отсева равна 11/15=0.73333(3).

непойму , какой смысл в формуле , если можно легко сделать общую долю отсева 0.5 проверяя только нечетные числа..

Для программной проверки на простоту:
// language C#
int IsProstoe = ...; // Объявляется переменная с числом.
// Проверяется делимость на два. % - деление по модулю.
if ((IsProstoe % 2) == 0)
{
MessageBox.Show ("Не простое!");
}

for (i = 3; i != (IsProstoe / 2); i+2)
{
if ((IsProstoe % i) == 0)
{
MessageBox.Show ("Не простое!");
}
}
Суть действия:
Сначала для быстроты исполнения проверяется на 2. -50% случайных чисел.
Затем идёт перебор для нечётных чисел, больших еденицы и меньших половины числа.
По-моему, хоть это и не самый, возможно, быстрый код, но он надёжен и прост в реализации, а затем будущим программерам в него будет легко въехать (начиная от таких, как я, 10-классников).
Для поиска вводится цикл, в который это помещается.
int MaxProstoe = ...;
for (int IsProstoe = 1; IsProstoe != MaxProstoe)
{...}

Это сообщение отредактировал(а) III.nfo - 19.10.2004, 20:42

Во-первых, 1 - не простое...
Люди не в курсе где можно найти Кнута в электронном виде? А то вы тут его вспоминали...

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

А по Эратосфену я сам писал. Нашёл все в пределах 80 000 000 000.

У меня даже прога валяется где-то (и работает в пределах 20 минут на 400 МГц). Если интересно...

Помоему этот попроще будет))... И ищет не только в сотне. И в 1000000 нейдёт... всё простые, только немного подождать придётся . Зацените.
Program gen;
uses crt;
var
n,k,t,sum,m: longint;
begin
clrscr;
textcolor (2);
sum:=0;
Read (m);
for n:=1 to m do
begin
t:=1;
k:=2;
while (k<n-1) and (t<>0) do
begin
t:=n mod k;
k:=k+1;
end;
if t=0 then
write ('')
else
begin
Write (' ',n);
inc(sum);
end;
end;
writeLn;
writeLn (sum);
readkey;
end.

Кнута здесь посмотреть  можно

http://www.poiskknig.ru/

Добавлено через 2 минуты и 16 секунд
А можно так, хотя почти тоже самое
Delphi:

Можно, и я свою лепту внесу    
язык Haskell.
Потенциально бесконечная последовательность простых чисел, используется классическое определение простого числа:

Пример взят отсюда.

Потенциально бесконечная последовательность простых чисел, используется решето Эратосфена:

пример мой.

sorry

Еще есть полином Мятисевича (как раз тут и обсуждался) только ничего разумного по нему найти не могу. Кто найдет- дам плюсик )

есть еще косвенные методы) сейчас к примеру иногда используется малая теорема ферма за исключением чисел кармайкла. Только для этого нужны компьютеры побольше   

Это сообщение отредактировал(а) Julius - 10.1.2010, 13:56

этот алгоритм ничем не отличается от самого тривиального алгоритма
b[z] = (a[z]-((i-a[z])/2%a[z]))%a[z] // при проверке на равенство нулю
b[z] = a[z]-((i-a[z])/2%a[z])  // после проверки
(a[z]-((i-a[z])/2%a[z]))%a[z] = 0 <=> 
i-a[z]=0(mod 2*a[z]) <=> 
cуществует такое k (1+2*k - нечётное, чётные можно не проверять), при котором i=a[z]*(1+2*k) 
// % - остаток от деления
если заменить 
if b[z] = 0 then begin
на
if i Mod a[z] = 0 then begin
то алгоритм очевидно будет работать от определения простого числа...

Это сообщение отредактировал(а) ProgBeat - 7.8.2007, 02:07