Спасибо 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.