Цитата:
|
Сообщение от Sweet_blood
Определите наибольшее простое число, меньшее 10000.
|
Наверное самый быстрый способ - с помощью
Решета Эратосфена, но он требует массива соответствующего размера:
Код:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | 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;
|
Простым перебором - более медленный способ, зато не требует дополнительной памяти:
Код:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | 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;
|
Правда этот способ можно слегка оптимизировать исключая чётные числа, но пусть это будет домашним заданием
06.05.2014, 21:13
решить в PascalABC.NET
Линейный вид
