Дана задача:
Любимые числа Деда Мороза
Дед Мороз любил развлекаться с числами и цифрами. Более всего он любил цифру 1, ведь именно 1.01 начинается Новый Год. Шли годы, но он так и остался суеверным - он не любил чисел, у которых после 1 стоит 3, то есть образуется число 13. На Новый Год он решил дать новое задание: посчитать, сколько любимых Дедом Морозом простых чисел есть на промежутке [А,В]?
Технические условия. Вход: Единственная строка, содержащая 2 числа: начало и конец заданного промежутка.
1 < = А,В < = 500000
Выход: Единственное число - количество любимых Дедом Морозом простых чисел.
Задача решена. Решена вроде как правильно.
Помогите сократить время выполнения алгоритма, при входных числах, скажем 10000 и 500000. Возможно кто-то в алгоритме найдёт баг.
Буду благодарен за любую подсказку.
Код:
var
f,f1:text;
a,b,i,count,e:integer;
m:string;
function prost(var ch:integer):boolean;
var
z,r:integer;
begin
z:=ch;
r:=2;
while (sqr® <= z) and (z mod r <> 0) do inc®;
Prost:=(sqr® > z);
if z=1 then Prost:=false;
end;
begin
count:=0;
assign(f, 'input.txt');
assign(f1,'output.txt');
reset(f);
rewrite(f1);
readln(f,a,b);
if a>b then
begin
e:=b;
b:=a;
a:=e;
end;
for i:=a to b do
begin
e:=i;
if Prost(e) then
begin
Str(e,m);
if Pos('13',m)=0 then inc(count);
end;
end;
writeln(f1,count);
close(f);
close(f1);
end.
P.S. Пробовал исключить из алгоритма поиска простых чисел все чётные числа, кроме 2. Толкового мало чего получилось..