ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      11 Jan 2002  23:14:04
 To : Sergey Politov
 Subject : простые числа
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Sergey Politov to Ivan Bessarabov:
 
  IB>> Расскажите, пожалуйста, про алгоритмы нахождения простых чисел и
  IB>> проверки чисел на простоту. И, если не сложно, расскажите,
  IB>> пожалуйста, где об этом можно почитать. Спасибо большое.
 
  SP>   ИМХО самый хороший способ нахождения простых чисел - "решето
  SP> Эратосфена".
 
 Большие простые числа ты таким образом не найдешь. О современных алгоритмах
 генерации/проверки больших простых чисел читайте в статье 
 Ю.В.Hестеренко "Алгоритмические проблемы теории чисел"
 http://www.mccme.ru/free-books/matpros3.html
 
  SP> Идея: заполняем массив единичками, бежим по этому
  SP> массиву, начиная со второго элемента, пока не найдем единичку, пусть
  SP> эта единичка оказалась на месте номер i, тогда с шагом i бежим по
  SP> массиву, и проставляем в те эл-ты 0, т.е. зануляем эл-ты номер
  SP> 2i,3i,4i,5i,6i... бежим по массиву дальше и ищем следующую единичку.
  SP> В результате если число p простое то в нашем массиве на p-м месте
  SP> будет 1, в противном случае 0.
 
  SP> Вот реализация:
 
 Твою реализацию можно существенно ускорить.
 
  SP> {$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
  SP> {$M 16384,0,655360}
  SP> const
  SP>   n = 1000;
  SP> var
  SP>   i,j: integer;
  SP>   a: array[2..n] of byte;
  SP> begin
  SP>   fillchar(a,sizeof(a),1);
  SP>   for i:= 2 to n shr 1 do if a[i]=1 then
 
 во-первых, бежать достаточно до sqrt(n), что значительно меньше n/2.
 
    for i:= 2 to trunc(sqrt(n)) do if a[i]=1 then
 
  SP>   begin
  SP>     j:= 2*i;
 
 во-вторых, начинать можно с i^2.
 
      j:= i*i;
 
  SP>     while j<=n do
  SP>     begin
  SP>       a[j]:= 0;
  SP>       inc(j,i);
  SP>     end;
  SP>   end;
  SP>   for i:= 2 to n do if a[i]=1 then write(i,#32);
  SP>   writeln;
  SP> end.
 
 Оба усовершенствования базируются на том факте, что у составного числа всегда
 есть делитель не превышающий корня из числа.
 
  SP> А вот как проверить я не знаю(при больших числах), можно конечно малую 
  SP> теорему Ферма использовать, но ведь и числа Карлмайкла есть. Что то
  SP> слышал,  про ро эвристику, но что это такое не помню.
 
 Читай в указанной статье алгоритм Милера-Рабина.
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.7
  * Origin:  (2:5015/60)
 
 

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

Тема:    Автор:    Дата:    простые числа   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