ac1010.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1010;
const
  max=999999;
  bitmask:array[0..7]of byte=(127,191,223,239,247,251,253,254);
  rightmask:array[0..8]of byte=(255,127,63,31,15,7,3,1,0);
var
  bits:array[0..255]of byte;
  prime:array[0..max shr 3]of word;
  count:array[0..max shr 3]of longint;
  m,n,q1,q2,r1,r2:longint;
procedure calbits;
  var
    i,j,x:byte;
  begin
    for i:=0 to 255 do begin
      x:=i;
      for j:=1 to 8 do begin
        if odd(x) then inc(bits[i]);
        x:=x shr 1;
      end;
    end;
  end;
procedure delprime(x:longint);
  var
    q,r:longint;
  begin
    q:=x shr 3;r:=x and 7;
    if prime[q] and bitmask[r]<prime[q] then dec(count[q]);
    prime[q]:=prime[q] and bitmask[r];
  end;
procedure calprime;
  var
    i,j:longint;
  begin
    fillchar(prime,sizeof(prime),255);
    for i:=0 to max shr 3 do count[i]:=8;
    delprime(0);delprime(1);
    for i:=2 to trunc(sqrt(max)) do begin
      j:=i shl 1;
      while j<=max do begin
        delprime(j);
        inc(j,i);
      end;
    end;
    for i:=1 to max shr 3 do inc(count[i],count[i-1]);
  end;
begin
  calbits;
  calprime;
  repeat
    read(m,n);
    q1:=m shr 3;r1:=m and 7;q2:=n shr 3;r2:=n and 7;
    writeln(count[q2]-count[q1]+bits[prime[q1] and rightmask[r1]]-bits[prime[q2] and rightmask[r2+1]]);
  until seekeof;
end.