记录编号	48279	评测结果	AAAAAAAAAA
题目名称	整数合并	最终得分	100
用户昵称	Vow Ryan	是否通过	通过
代码语言	Pascal	运行时间	0.028 s
提交时间	2012-11-05 14:07:49	内存使用	1.05 MiB

var
 f:array[0..210000]of longint;
 v:array[0..210000]of boolean;
 i,j,k,l,m,n,r,p,st,ed,x,y,ans:longint;

function find(x:longint):longint;
 begin
  if f[x]=x then exit(x);
  f[x]:=find(f[x]);
  exit(f[x]);
 end;

begin
 assign(input,'setb.in');reset(input);
 assign(output,'setb.out');rewrite(output);
 read(l,r,p);
 
 for i:=2 to r do v[i]:=true;
 i:=1;
 while i<r do
  begin
   inc(i);
   for j:=2 to r div i do v[i*j]:=false;
  end;
 
 for i:=l to r do f[i]:=i;
 
 for i:=p to r do
  if v[i] then
   begin
    st:=l div i;
    ed:=r div i;
    for j:=st to ed-1 do 
     if (j*i>=l)and(j*i<=r) then 
      begin
       k:=j+1;
       if (k*i>=l)and(k*i<=r) then 
        begin
         x:=find(j*i);y:=find(k*i);
         f[x]:=y;
        end;
      end;
   end;
 
 for i:=l to r do
  if f[i]=i then inc(ans);
 writeln(ans);
 close(output);
end.