记录编号	48345	评测结果	AAAAAAAAAA
题目名称	整数合并	最终得分	100
用户昵称	张来风飘	是否通过	通过
代码语言	Pascal	运行时间	0.026 s
提交时间	2012-11-05 16:02:57	内存使用	0.54 MiB

program Project1;
var a,b,p:longint;
    f:array[0..100005] of longint;
function find(x:longint):longint;
begin
     if f[x]<>x then f[x]:=find(f[x]);
     exit(f[x]);
end;
procedure init;
var i:longint;
begin
     assign(input,'setb.in');reset(input);
     assign(output,'setb.out');rewrite(output);
     read(a,b,p);
     for i:=a to b do f[i]:=i;
end;
function ss(x:longint):boolean;
var i:longint;
begin
     if x=1 then exit(false);if x=2 then exit(true);
     for i:=2 to trunc(sqrt(x)) do
         if x mod i=0 then exit(false);
     exit(true);
end;
procedure main;
var k,ans,i:longint;
begin
     repeat
           if not ss(p) then
           begin
                inc(p);
                continue;
           end;
           k:=a div p;
           if k*p<a then inc(k);
           while (k+1)*p<=b do
           begin
                if find(k*p)<>find((k+1)*p) then f[find(k*p)]:=find((k+1)*p);
                inc(k);
           end;
           inc(p);
     until p>b shr 1;
     ans:=0;
     for i:=a to b do if f[i]=i then inc(ans);
     writeln(ans);
     close(input);
     close(output);
end;
begin
     init;
     main;
end.