[poli-smen]

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

Определите наибольшее простое число, меньшее 10000.

Наверное самый быстрый способ - с помощью Решета Эратосфена, но он требует массива соответствующего размера:

Код:

procedure TForm1.Button1Click(Sender: TObject);
const
  max = 10000;
var
  nums: array [2..max] of Boolean;
  i, j: Integer;
begin
  for i := 2 to max do
    nums[i] := True;

  for i := 2 to max do
  begin
    if nums[i] then
    begin
      j := i + i;
      while j <= max do
      begin
        nums[j] := False;
        Inc(j, i);
      end;
    end;
  end;

  for i := max downto 2 do
  begin
    if nums[i] then
    begin
      ShowMessageFmt('Число %d является наибольшим простым числом которое не превышает %d', [i, max]);
      Break;
    end;
  end;
end;

Простым перебором - более медленный способ, зато не требует дополнительной памяти:

Код:

procedure TForm1.Button2Click(Sender: TObject);
const
  max = 10000;
var
  i, j: Integer;
  IsPrime: Boolean;
begin
  for i := max downto 3 do
  begin
    IsPrime := True;
    for j := 2 to Trunc(Sqrt(i)) do
    begin
      if (i mod j) = 0 then
      begin
        IsPrime := False;
        Break;
      end;
    end;

    if IsPrime then
    begin
      ShowMessageFmt('Число %d является наибольшим простым числом которое не превышает %d', [i, max]);
      Break;
    end;
  end;
end;

Правда этот способ можно слегка оптимизировать исключая чётные числа, но пусть это будет домашним заданием