Pascal - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Pascal (http://forum.oszone.net/showthread.php?t=149518)

Имеется задача:
http://imageban.ru/show/2009/09/01/2...a22e13c429/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 секунд!
Как с этим бороться?

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

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

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

Также смотрим:Решето_Эратосфена и
http://www.helloworld.ru/texts/comp/...mple/index.htm

Цитата:

Цитата ManHack

Как с этим бороться? »

Оптимизировать алгоритм :)
Расставь комментарии пожалуйста. Или опиши применяемый метод.

Цитата:

Цитата ManHack

Код:

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 и т.д. Не проще ли сразу на них проверить?