ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Politov                       2:5015/176.18  12 Jan 2002  06:02:18
 To : Ivan Bessarabov
 Subject : Re: простые числа
 -------------------------------------------------------------------------------- 
 

 
 До меня дошли слухи, что *11.01.02* *2:00:34* пролетало сообщение
 от Ivan к *All* про *"простые числа"*. И я решил вмешаться.
 
  IB> Расскажите, пожалуйста, про алгоритмы нахождения простых чисел и проверки
  IB> чисел на простоту. И, если не сложно, расскажите, пожалуйста, где об этом
  IB> можно почитать. Спасибо большое.
 
   ИМХО самый хороший способ нахождения простых чисел - "решето Эратосфена".
 Идея:
 заполняем массив единичками, бежим по этому массиву, начиная со второго
 элемента,
 пока не найдем единичку, пусть эта единичка оказалась на месте номер i, тогда с
 шагом i бежим по массиву, и проставляем в те эл-ты 0, т.е. зануляем эл-ты номер
 2i,3i,4i,5i,6i... бежим по массиву дальше и ищем следующую единичку. В
 результате
 если число p простое то в нашем массиве на p-м месте будет 1, в противном
 случае 0.
 
 Вот реализация:
 {$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
 {$M 16384,0,655360}
 const
   n = 1000;
 var
   i,j: integer;
   a: array[2..n] of byte;
 begin
   fillchar(a,sizeof(a),1);
   for i:= 2 to n shr 1 do if a[i]=1 then
   begin
     j:= 2*i;
     while j<=n do
     begin
       a[j]:= 0;
       inc(j,i);
     end;
   end;
   for i:= 2 to n do if a[i]=1 then write(i,#32);
   writeln;
 end.
 
 А вот как проверить я не знаю(при больших числах), можно конечно малую 
 теорему Ферма использовать, но ведь и числа Карлмайкла есть. Что то слышал, 
 про ро эвристику, но что это такое не помню.
 
 np: Helloween "Ride The Sky"
 
 Искренне Ваш
                Sergey Politov
 
 --- WP/95 Rus 1.78 Релиз 1  Reg.
  * Origin: Metal Invaders. (2:5015/176.18)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    простые числа   Ivan Bessarabov   11 Jan 2002 03:00:34   Re: простые числа   Sergey Politov   12 Jan 2002 06:02:18   простые числа   Max Alekseyev   11 Jan 2002 23:14:04