Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Решето Эратосфена

Автор: poc 21.4.2004, 11:52

Привет Всем!
Кто нибудь может написать код нахождения 10000 простых чисел?
Спасибо!

Автор: maxim1000 21.4.2004, 12:25

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

Автор: Maverick 21.4.2004, 13:09

Насколько, я помню.... Простое - это которое делится нацело только на себя и на 1, значит....

for cislo :=1 to 10 000 do begin
count := 0; //количество делителей нацело
for delit:= 1 to cislo do if int(cislo/delit)=cislo/delit then count:=count+1;
//есть и более умные способы проверить делимость нацело, но счас в голову не приходят...
if count<=2 then //действия по запоминанию этого числа, cislo заносится в массив, например....
end;

вот что-то такое....

Автор: Гость_Oxygen 23.4.2004, 16:13

Я чуть поправлю Maverick`a.

Вместо:
for delit:= 1 to cislo do if int(cislo/delit)=cislo/delit then count:=count+1;

Ставим:
for delit:= 1 to sqrt(cislo) do if int(cislo/delit)=cislo/delit then count:=count+1;

Такой алгоритм быстрее

Автор: OxygenZ 23.4.2004, 17:02

Чоссс:
Во как нужно -->

for delit:= 1 to round(sqrt(cislo)) do if int(cislo/delit)=cislo/delit then count:=count+1;

Автор: Magister Y0da 12.1.2007, 13:00

Конечно алгоритм верный (round(sqrt(cislo))), но зачем делать лишнюю работу???

Код


if cislo mod 2 <>0 then
begin
b:=true;
for delit:=2 to round(sqrt(cislo)) do
if int(cislo/delit)=cislo/delit then
begin
b:=false;
break;
end;
if b then writeln(cislo);
end;