Большие числа

[iskander]

Совсем забыл что вторая задача так и оставалась без решения.
Спасибо xdsl и Alex2013 напомнили.
(условие: на промежутке А, В подсчитать количество простых чисел , 1 сек, 256 МiБ; 1 ≤ A ≤ 10е12, A ≤ B, B − A ≤ 2*10е6.)

Код: Выделить всё

program primes;

{$mode objfpc}

type
  TBoolArray = array of Boolean;

function CreateBoolArray(aSize: Integer; aValue: Boolean): TBoolArray;
begin
  SetLength(Result, aSize);
  FillChar(Pointer(Result)^, aSize, aValue);
end;

function RangeCount(Lower, Upper: Int64): Integer;
var
  FirstPrimes: array of Integer = nil;

  procedure Sieve(Upper: Integer);
  var
    IsPrime: TBoolArray = nil;
    I, Count: Integer;
    J: Int64;
  begin
    SetLength(FirstPrimes, Upper);
    IsPrime := CreateBoolArray(Upper + 1, True);
    Count := 0;
    for I := 2 to Upper do
      if IsPrime[I] then
        begin
          FirstPrimes[Count] := I;
          Inc(Count);
          J := Int64(I) * Int64(I);
          while J <= Upper do
            begin
              IsPrime[J] := False;
              Inc(J, I);
            end;
        end;
    SetLength(FirstPrimes, Count);
  end;

var
  IsPrime: TBoolArray = nil;
  R, I, CurPrime: Integer;
begin
  Sieve(Trunc(Sqrt(Upper)) + 1);
  R := Upper - Lower;
  Result := R + 1;
  IsPrime := CreateBoolArray(Result, True);
  for CurPrime in FirstPrimes do
    begin
      I := Lower mod CurPrime;
      if I <> 0 then
        I := CurPrime - I;
      while I <= R do
        begin
          if IsPrime[I] then
            begin
              IsPrime[I] := False;
              Dec(Result);
            end;
          I += CurPrime;
        end;
    end;
end;

function SieveCount(Lower, Upper: Integer): Integer;
var
  IsPrime: TBoolArray = nil;
  I: Integer;
  J: Int64;
begin
  IsPrime := CreateBoolArray(Upper + 1, True);
  Result := 0;
  for I := 2 to Upper do
    if IsPrime[I] then
      begin
        if I >= Lower then
          Inc(Result);
        J := Int64(I) * Int64(I);
        while J <= Upper do
          begin
            IsPrime[J] := False;
            Inc(J, I);
          end;
      end;
end;

const
  MAX_A    = 1000000000000;
  MAX_DIFF = 2000000;

var
  A, B: Int64;
  Count: Integer;

begin
  ReadLn(A, B);
  if (A < 1) or (B <= A) then
    begin
      WriteLn('Wrong input');
      Halt;
    end;
  if (A > MAX_A) or (B - A > MAX_DIFF) then
    begin
      WriteLn('Limit violation');
      Halt;
    end;
  if Trunc(Sqrt(B)) + 1 >= A then
    Count := SieveCount(A, B)
  else
    Count := RangeCount(A, B);
  WriteLn(Count);
end.