Нахождение простых чисел

[Marik]

Господа, не подскажите реализацию алгоритма "решета Эратосфена" для компьютера? Или другого хорошего алгоритма нахождения простых чисел?

[XPOHOC]

Marik

легко. тебе на словах принцип или исходник на языке?

[Marik]

Исходник желательно.

[XPOHOC]

Marik

текст на Delphi.

{$APPTYPE CONSOLE}

 

const MAX_NUM = 1000;

var

  PrimeNumbers : array [1..MAX_NUM] of integer;

  PrimeCount : integer;

 

function IsPrime (Cand : integer) : boolean;

var i:integer;

begin

  result := true;

  for i := 1 to PrimeCount do

    if (Cand mod PrimeNumbers) = 0 then

result := false;

end;

 

var

  Candidate,i : integer;

begin

  PrimeCount := 0;

  for Candidate := 2 to MAX_NUM do begin

    if IsPrime (Candidate) then begin

      inc (PrimeCount);

      PrimeNumbers[PrimeCount] := Candidate;

    end;

  end;

 

 

  for i := 1 to PrimeCount do

    write (PrimeNumbers,' ');

end.

[Marik]

Спасибо за помощь, но этот алгоритм явно не подходит.

Медленнее последовательного перебора быть ничего не может Мне же нужен алгоритм побыстрее, поэтому я и заговорил про решето Эратосфена (или какой-то другой оптимизированный алгоритм)

[AL-GALI]

Кажется, это и есть то самое решето: проверка на делимость простыми числами менее проверяемого.

[Большой и черный]

Marik

Врядли ты что-нибудь еще найдешь. Эратосфен, наверное, -- единственный метод "с гарантией". В криптографии применяются быстрые методы проверки простоты, но они вероятностные (самые простые используют Малую Теорему Ферма), что тебе не подходит.

[Marik]

AL-GALI

Суть решета Эратосфена - исключение чисел кратных уже найденным простым числам. Я знаю лишь математическую модель. Понимаю, что реализовать данный алгоритм не получится, поэтому и поинтересовался, существуют ли более оптимизированные алгоритмы, чем предложенный тобой (самый очевидный).

 

Большой и черный

А где бы почитать про эти самые методы?

[tremp]

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

[Marik]

tremp

Нет, ввести статистически нельзя. Нужны действительно большие простые числа. Заказчик ПО захотел шифрование. А я, балбес такой, не хочу пользоваться имеющимися библиотеками.

[Большой и черный]

Marik

 

Используй www.google.com . Гугл по поиску "prime numbers search" сразу выдает множество ссылок на статьи. Например, вот короткое и простое описание алгоритма Рабина-Миллера, который применяется в Mathematica. Заходи и читай:

 

_http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

 

Что касается книг на русском (если таковых нет дома или в библиотеке), то ты можешь скачать книжки по криптографии с "Колхоза": _http://lib.homelinux.org . Их там несколько штук, разного уровня сложности. Или еще можешь поискать ссылки на файлообменниках. Например, вот:

 

В.В. Ященко

Введение в криптографию

Изд-во: ЧеРо, 1999. - 271 стр.

 

_http://rapidshare.de/files/25797097/Vvedenie.v.kriptogragiju.rar