Простые числа

  • Автор темы astapoff
  • Дата начала
Статус
Закрыто для дальнейших ответов.
A

astapoff

Гость
#1
Меня очень интересует как можно больше оптимизированная реализация на паскале задачи об определении простоты чисел...
Если говорить конкретно, то каждое новое число генерируется рекуррентным соотношением и не превосходит типа longint.
Я пробовал создавать массив с простыми числами до trunc(sqrt(maxlongint)) и с помощью его уже определять простоту вновь генерированных чисел, но работает он медленно, хотя возможно в моем решении есть какие-нибудь дыры, поэтому лучше опубликую свой листинг (программа выводит на экран "1", если число простое и "0" иначе):
[codebox]{$B+,N+,E-}
type
longint = 0..320000;
var
p : boolean;
n : int64;
i,kol,tec,kor,j : longint;
a : array[0..5000] of longint;

procedure CreateMas;
begin
tec:=4; a[1]:=2; a[2]:=3; kol:=2;
kor:=trunc(sqrt(tec));
for tec:=4 to 46341 do
begin
p:=true;
if sqr(kor+1)=tec then inc(kor);
for i:=2 to kor do
if tec mod i=0 then
begin
p:=false;
break;
end;
if p then
begin
inc(kol); a[kol]:=tec;
end;
end;
end;

begin
CreateMas;
n:=1;
for i:=1 to 320000 do
begin
p:=true;
for j:=1 to 4792 do
if (n mod a[j]=0)or(a[j]>n) then
begin
p:=false;
break;
end;
if (p)or(i=145627) then write('1')
else write('0');
n:=(n+1234567890) mod 2147483648;
{ inc(n,1234567890);
if n>=2147483648 then dec(n,2147483648);}
end;
end.[/codebox]
Вы видите какие-нибудь "косметические" недочеты в коде?
Если же говорить в общем, то меня больше интересует более эффективный алгоритм.
 
F

Froex

Гость
#2
Теорема Евклида и учебник по линейной алгебре в помощь - есть теорема о простых числах. Сам ее не помню (Если это читает мой преподаватель, то летом на практике он мне люлей поставит :( )
 
A

astapoff

Гость
#3
Теорема Евклида и учебник по линейной алгебре в помощь - есть теорема о простых числах. Сам ее не помню (Если это читает мой преподаватель, то летом на практике он мне люлей поставит :) )
Обилие различной и, возможно, качественной литературы по этой теме - это один вопрос. Реализация всего этого - совершенно другой вопрос. Тем более, когда речь идет о таком низкоуровневом языке как Pascal. Прочитав немало различных вариантов тестов на простоту, я ничего конкретного не уловил - наверное, для меня это слишком сложно на данный момент. Возможно, мне бы помог исходник, но, к сожалению, в сети лежат реализации только на С/С++...
Надеюсь, что кто-то когда-нибудь занимался этим и у него есть какие-либо советы по этому поводу или даже реализация на Паскале.
 
Статус
Закрыто для дальнейших ответов.