Pascal

[ManHack]

Имеется задача:
http://imageban.ru/show/2009/09/01/2ac095cf74ec49d840f3f1a22e13c429/jpg


Код написан:
{$N+,E-}
program book1;
var
m, n: 2..300000;
input, output: text;
absent: boolean;
i, j, root, divisor: longint;
prim: boolean;
begin
assign (input, 'primes.in');
reset (input);
assign (output, 'primes.out');
rewrite (output);
absent := true;
while not eof(input) do
readln (input, m, n);
i := m;

{ while i < n do begin
prim := true;

for j:= 2 to root do
if (i mod j = 0) and (i <> j) then
prim := false;
if prim then begin
writeln (output, i);
absent := false;
end;
i := i + 1;
end; }
while i < n do begin
root := trunc(sqrt(i));
divisor := 2;
prim := true;
while (divisor <= root) and prim do begin
if i mod divisor <> 0 then
prim := false;
divisor := divisor + 1;
end;
if prim then
write (output, i, ' ');
end;
if absent then
writeln (output, 'Absent');

writeln ('All done.');
end.
(вроде это та версия... ^^)

А теперь главное: ограничения программы указываются для компьютера Intel Celeron 400.

Программа при M и N близких к граничным значениям работает куда больше 6 секунд!
Как с этим бороться?

[BlackEric]

Чем вы компилируете и под какой ОС и на какой машине запускаете?

И дайте пример файла primes.in на котором тормозит.

divisor := divisor + 1; - заменяем на inc(divisor);
И освобождаем ресурсы!

Также смотрим:Решето_Эратосфена (http://ru.wikipedia.org/wiki/Решето_Эратосфена) и
http://www.helloworld.ru/texts/comp/algor/chisl/simple/index.htm

[lxa85]

Как с этим бороться? »
Оптимизировать алгоритм :)
Расставь комментарии пожалуйста. Или опиши применяемый метод.while (divisor <= root) and prim do begin
if i mod divisor <> 0 then
prim := false;
divisor := divisor + 1;
end; »
Т.е. для проверки n'ой цифры на предмет простоты необходимо проделать
T=n/2+n/3*2)+E{n/i-2} 5<i<sqrt(n) сравнений? где i - простое. E - сумма.
сравнений?
Не лень алгоритму будет подниматься каждый раз снизу вверх проходя каждый каждый 3 раз 1 лишний цикл, каждый 5 ый - 3 и т.д. ?
Я подвожу к той мысли, что в памяти мы вроде как не сильно ограничены. Примени массив простых чисел и сверяй с ним! Зачем по 100 раз совершать ненужные действия? Для i=123 будут проверены ВСЕ! числа включая все кратные 2,3,5,7,11,13,17,19,23 и т.д. Не проще ли сразу на них проверить?