记录编号	57748	评测结果	AAAAAAAAAA
题目名称	整数合并	最终得分	100
用户昵称	joeyolui	是否通过	通过
代码语言	Pascal	运行时间	0.025 s
提交时间	2013-04-12 16:38:12	内存使用	1.02 MiB

var
father,pri:array[1..100001] of longint;
bool:array[1..100001] of boolean;
a,b,p,i,j,ans,tot:longint;

function getfather(v:longint):longint;
begin
if father[v]=v then exit(v) else father[v]:=getfather(father[v]);
exit(father[v]);
end;

procedure union(x,y:longint);
var
fx,fy:longint;
begin
fx:=getfather(x);
fy:=getfather(y);
if fx<>fy then father[fx]:=fy;
end;

procedure prime;
var
i,j:longint;
begin
fillchar(bool,sizeof(bool),true);
for i:=2 to trunc(sqrt(b)) do
 if bool[i] then
  begin
  j:=i;
  while j+i<=b do
   begin
   j:=j+i;
   bool[j]:=false;
   end;
  end;
tot:=0;
for i:=p to b do
 if bool[i] then
  begin
  inc(tot);
  pri[tot]:=i;
  end;
end;

function gcd(x,y:longint):longint;
begin
if x mod y=0 then exit(y) else exit(gcd(y,x mod y));
end;

function same(x,y:longint):boolean;
begin
if getfather(x)=getfather(y) then exit(true) else exit(false);
end;

procedure find;
var
i,j:longint;
begin
for i:=1 to tot do
 begin
 if a mod pri[i]=0 then j:=a else j:=((a div pri[i])+1)*pri[i];
 while j+pri[i]<=b do
  begin
  if not same(j,j+pri[i]) then
   begin
   union(j,j+pri[i]);
   dec(ans);
   end;
  j:=j+pri[i];
  end;
 end;
end;

begin
assign(input,'setb.in'); assign(output,'setb.out');
reset(input); rewrite(output);
readln(a,b,p);
for i:=a to b do
 father[i]:=i;
ans:=b-a+1;
fillchar(pri,sizeof(pri),0);
prime;
find;
writeln(ans);
close(input); close(output);
end.