печатающую все простые числа

[Сергей505]

Составить программу на турбо паскале: напишите программу, печатающую все простые числа, не превосходящие данного числа.

[Hemul]

в for прокрути от 0 но N и каждое число проверяй на простоту
например по функции

bool prost(int p)
{
    bool is_prime = true;
    for(int i=2;i <= sqrt(p); ++i)
        if( p % i == 0 ) is_prime=false;
    return is_prime;
}

еще существует формула определения простоты для числа p
fact(p-1) + 1 mod p = 0 - число простое

[Serge_Bliznykov]

function isPrime(X: LongInt): boolean;
var i: integer;
Begin
     isPrime:=false;
     if x<2 then Exit;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     while i <= sqrt(x) do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
     isPrime:=true;
End;
var i, N : longint;
begin
   WriteLn('Введите N');
   for i:=1 to N do 
     if  isPrime(i) then Write(i,'  ');
   WriteLn;
   readln;
end.

[TinMan]

Серж, ты забыл вводить N

Вообще, не совсем все же правильно делать так - проверять в цикле все числа на простоту. Ведь при проверке каждого числа приходится всю работу проводить заново.. Вообще, хотя эти две задачи: проверка на простоту и поиск всех простых - конечно, очень близки, с точки зрения производительности их следует все же разделять. Более естественный и эффективный способ поиска простых известен со времен древних греков - т.н. Решето Эратосфена. Принцип очень прост, но проблема в том, что ему надо много памяти. Это проявление общей закономерности: либо быстро, либо компактно .

Я вот состряпал прожку, которая использует по одному биту на число:

{ finding prime numbers using Sieve of Eratosthenes
  by TinMan, programmersforum.ru }

const
  q= 256;

var
  a: array of set of byte;
  i,j,m,n: LongInt;
  b: set of byte;

begin
  write('enter a number: ');
  readln(n);
  SetLength(a,n div q+1);
  a[0]:= [0,1];
  for i:=2 to n do
    if not ((i mod q) in a[i div q]) then begin
      j:= i;
      while j<=n-i do begin
        j:= j+i;
        Include(a[j div q],j mod q);
      end
  end;
  for i:=0 to n div q do begin
    if i=n div q then m:= n mod q else m:= q-1;
    for j:=0 to m do
      if not (j in a[i]) then writeln(i*q+j)
    end;
end.

Выигрыш в скорости проявляется при больших числах. Например, при n=10^7, она считает (на моем компе) примерно 10 сек, а прога с проверкой каждого числа - 8 мин. Понятно, что относительное различие будет расти с ростом диапазона.
Конечно, обе проги можно еще оптимизировать, но все же общий результат останется тем же.

[Serge_Bliznykov]

Сообщение от TinMan

Серж, ты забыл вводить N

угу. точно. там пропущено Readln(N);
я это сделал не специально, но пусть это будет заданием для того, кто попытается использовать данный код.

Сообщение от TinMan

Вообще, не совсем все же правильно делать так - проверять в цикле все числа на простоту.

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


TinMan, спасибо за замечание и код программы.