记录编号	119871	评测结果	AAAAAAAAAA
题目名称	整数合并	最终得分	100
用户昵称	helloworld123	是否通过	通过
代码语言	Pascal	运行时间	0.063 s
提交时间	2014-09-14 17:41:11	内存使用	0.51 MiB

program cogs487;
const
 maxn=100000;
var
  i,j,l,r,p,ans,x:longint;
  fa:array[1..maxn] of longint;
  f:array[1..maxn] of boolean;
function find(x:longint):longint;
var
  i:longint;
begin
  if fa[x]=x then exit(x);
   i:=find(fa[x]);
   fa[x]:=i;
  exit(i);
end;
procedure combine(i,j:longint);
var
  x,y:longint;
begin
  x:=find(i);
  y:=find(j);
  if x<>y then
   begin
    fa[x]:=y;
   end;
end;
begin
 assign(input,'setb.in'); reset(input);
 assign(output,'setb.out'); rewrite(output);
  readln(l,r,p);
  for i:=1 to r do
     fa[i]:=i;
  f[1]:=true;
  for i:=2 to (r div 2) do
   if not f[i] then
    begin
	 x:=i;
	 while x<=r do
      begin
	   x:=x+i;
      if x<=r then
      begin
	   if not f[x] then
		 f[x]:=true;
		 if (i>=p)and(x<=r) then combine(i,x);
     end;
      end;
	end;
	
	ans:=0;
	
  for i:=l to r do
   if fa[i]=i then inc(ans);
  writeln(ans);
 close(input); close(output);
end.