Как сделать проверку числа на простоту?

Question

[kan3k1k3n]

у меня есть модуль на паскале, который делает проверку числа на простоту. если возвращается true, то значит число просто, иначе составное.

unit modul1;
INTERFACE
Function isPrime(n: integer): boolean;
IMPLEMENTATION
Function isPrime(n: integer): boolean; {Функция проверки числа n, n > 1, является ли n-e число - простым}
 Var i: Integer;
  flag: Boolean; {flag - true, n-e число - простое, false - составное}
 Begin
   flag:= True; {Предположение, что n-e число - prime}
   for i:= 2 to (n div 2) do
     if (n mod i = 0) then
       flag:= False;
       isPrime:= flag;{возврат true/false}
 End;
end.

как сделать, чтобы еще выводилась фраза "число простое", если значение true, и "число составное", если значение false?

Answer 1

[Hemul GM]

Вы издеваетесь?

if IsPrime(10) then
  Writeln('Простое')
else
  Writeln('Составное')

Comments

[kan3k1k3n]

ошибка "переполнение программного стека"

[Hemul GM]

kan3k1k3n, эта ошибка у вас не из-за этого кода. Т.е. не из-за модуля и функции и не из-за того, что я привел

[Hemul GM]

kan3k1k3n,
и ваша функция кривая. К ошибке не приводит, но она кривая. Должно быть примерно так

function IsPrime(n: integer): boolean;
var
  i: Integer;
begin
  for i := 2 to (n div 2) do
    if (n mod i = 0) then
      Exit(False);
  Result := True; {число - prime}
end;

[bormant]

Hemul GM,
но лучше так:

function IsPrime(n: Longint): Boolean;
var d, q: Integer;
begin
  IsPrime:=False;
  if (n<2) or (n<>2) and not Odd(n) then Exit;
  q:=Trunc(SqRt(n)); d:=3;
  while (d<=q) and (n mod d<>0) do Inc(d,2);
  if d<=q then Exit;
  IsPrime:=True;
end;

Или так:

function IsPrime(n: Longint): Boolean;
var i, sqrtn, delta: Word;
begin
  if (n >= 5) and ((n - 1) mod 6 = 0) or ((n + 1) mod 6 = 0) then begin
    i := 5;
    delta := 2;
    sqrtn := Trunc(sqrt(n));
    IsPrime := False;
    while i <= sqrtn do begin
      if n mod i = 0 then Exit;
      Inc(i, delta);
      delta := delta xor 6; {смена шага, то 2, то 4}
    end;
    IsPrime := True;
  end else
    IsPrime := (n = 2) or (n = 3);
end;

Или даже так:

function IsPrime(n: Longint): Boolean;
const delta: array [0..7] of Word = (4, 2, 4, 2, 4, 6, 2, 6);
var i, j, sqrtn: Word;
begin
  if (n >= 7) and ((n - 1) mod 6 = 0) or ((n + 1) mod 6 = 0) then begin
    i := 7; j := 0;
    sqrtn := Trunc(SqRt(n));
    IsPrime := False;
    while i <= sqrtn do begin
      if n mod i = 0 then Exit;
      Inc(i, delta[j]);
      Inc(j); if j = 8 then j := 0;
    end;
    IsPrime := True;
  end else
    IsPrime := (n = 2) or (n = 3) or (n = 5);
end;

Но если проверять несколько чисел, любое решето обычно быстрее.