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

Тема в разделе "Delphi - FAQ", создана пользователем astapoff, 11 мар 2008.

Статус темы:
Закрыта.
  1. astapoff

    astapoff Гость

    Меня очень интересует как можно больше оптимизированная реализация на паскале задачи об определении простоты чисел...
    Если говорить конкретно, то каждое новое число генерируется рекуррентным соотношением и не превосходит типа 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]
    Вы видите какие-нибудь "косметические" недочеты в коде?
    Если же говорить в общем, то меня больше интересует более эффективный алгоритм.
     
  2. Froex

    Froex Гость

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

    astapoff Гость

    Обилие различной и, возможно, качественной литературы по этой теме - это один вопрос. Реализация всего этого - совершенно другой вопрос. Тем более, когда речь идет о таком низкоуровневом языке как Pascal. Прочитав немало различных вариантов тестов на простоту, я ничего конкретного не уловил - наверное, для меня это слишком сложно на данный момент. Возможно, мне бы помог исходник, но, к сожалению, в сети лежат реализации только на С/С++...
    Надеюсь, что кто-то когда-нибудь занимался этим и у него есть какие-либо советы по этому поводу или даже реализация на Паскале.
     
Загрузка...
Похожие Темы - Простые числа
  1. Евгений1998
    Ответов:
    2
    Просмотров:
    1.456
  2. Cleric-Lviv
    Ответов:
    6
    Просмотров:
    2.782
  3. vital
    Ответов:
    10
    Просмотров:
    4.929
  4. areostar
    Ответов:
    0
    Просмотров:
    359
  5. Bisyara
    Ответов:
    0
    Просмотров:
    955
Статус темы:
Закрыта.

Поделиться этой страницей