记录编号	21003	评测结果	AAAAAAAAAA
题目名称	整数合并	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.038 s
提交时间	2010-11-02 11:20:58	内存使用	0.59 MiB

program setb;
var
  i,j,ans,a,b,p:longint;
  father:array [1..100000] of longint;
  use:array [1..100000] of boolean;
function getfather(root:longint):longint;
begin
  if (father[root]=root) then exit (root);
  father[root]:=getfather(father[root]);
  exit (father[root]);
end;
procedure judge(i,j:longint);
var a,b:longint;
begin
  a:=getfather(i);
  b:=getfather(j);
  father[b]:=a;
end;
procedure getprime;
var
  flag:array [1..100000] of boolean;
  i,t:longint;
begin
  fillchar (flag,sizeof(flag),0);
  for i:=2 to p-1 do begin
    if flag[i]=false then begin
	  t:=i+i;
      while t<=b do begin
	    flag[t]:=true;
	    t:=t+i;
      end;
	end;
  end;
  for i:=p to b do begin
    if flag[i]=false then begin
	  t:=i+i;
      while t<=b do begin
	    flag[t]:=true;
		judge(i,t);
	    t:=t+i;
      end;
	end;
  end;
end;
begin
  fillchar (use,sizeof(use),0);
  assign (input,'setb.in');
  reset (input);
  readln (a,b,p);
  for i:=1 to b do father[i]:=i;
  close (input);
  assign (output,'setb.out');
  rewrite (output);
  getprime;ans:=0;
  for i:=a to b do begin
    j:=getfather(i);
	if use[j]=false then begin
	  use[j]:=true;
	  inc(ans);
	end;
  end;
  writeln (ans);
  close (output);
end.