program Euler_Project3;
{$Mode objfpc}{$H+}
{The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?}
uses Types;
function GetPrimesBelow(anInt: Integer): TIntegerDynArray;
var
halfRange, i, num: Integer;
procedure Delete(j: Integer);
var
k: Integer;
begin
for k := j to High(Result)-1 do
Result[k] := Result[k+1];
SetLength(Result, Length(Result)-1);
end;
begin
halfRange:=anInt div 2;
case Odd(anInt) of
False: SetLength(Result, halfRange);
True: SetLength(Result, halfRange+1);
end;
i := 0;
for num := 2 to anInt do
if Odd(num) or (num = 2) then begin
Result[i] := num;
Inc(i);
end;
for num := halfRange downto 3 do
begin
if not (Odd(num) or (num = 2)) then
Continue;
for i := High(Result) downto Low(Result) do
if ((Result[i] mod num) = 0) and (Result[i] <> num) then
Delete(i);
end;
end;
var
a, aSqrt, x, product: Integer;
primeArray, primeFactors: TIntegerDynArray;
function IsPrime(anInt: Integer): Boolean;
var
i: Integer;
begin
for i in primeArray do
if i = anInt then
Exit(True);
Result := False;
end;
begin
a := 13195;
aSqrt := trunc(sqrt(a));
primeArray := GetPrimesBelow(aSqrt + 1);
SetLength(primeFactors, 0);
for x := 2 to aSqrt do
if IsPrime(x) and ((a mod x) = 0) then begin
SetLength(primeFactors, Length(primeFactors) + 1);
primeFactors[High(primeFactors)] := x;
end;
WriteLn('The prime factors of ',a,' are: ');
for x in primeFactors do
Write(x, ' ');
WriteLn;
product:=1;
for x in primeFactors do
product := product * x;
WriteLn('The product of the prime factors of ', a,' is ', product);
ReadLn;
end.