program cons;
{$APPTYPE CONSOLE}
{$R *.res}

uses
  System.SysUtils;

type
    TIntArray = array of Integer;

function FastExp(a, z, m: Int64): Integer;
var
    R: Int64;
begin
    R := 1;
    while z <> 0 do
    begin
        while (z and 1) = 0 do
        begin
            z := z shr 1;
            a := (a * a) mod m;
        end;
        z := z - 1;
        R := (R * a) mod m;
    end;
    Result := R;
end;

function Factorize(N: Integer): TIntArray;
var
    I, Count: Integer;
begin
    SetLength(Result, Trunc(Sqrt(N)));
    Count := 0;
    for I := 2 to Trunc(Sqrt(N)) do
    begin
        if N mod I = 0 then
        begin
            Result[Count] := I;
            Inc(Count);
            while N mod I = 0 do
                N := N div I;
        end;
    end;
    if N <> 1 then
    begin
        Result[Count] := N;
        Inc(Count);
    end;
    SetLength(Result, Count);
end;

function AnyPhi(N: Integer): Integer;
var
    Factors: TIntArray;
    I: Integer;
begin
    Result := N;
    Factors := Factorize(N);
    for I := Low(Factors) to High(Factors) do
    begin
        Result := Result * (Factors[I] - 1) div Factors[I];
    end;
end;

function FindPrimitiveRoots(P: Integer): TIntArray;
var
    Factors: TIntArray;
    G, I, Phi, Count: Integer;
    IsCorrect: Boolean;
begin
    Phi := P - 1;
    Count := 0;
    Factors := Factorize(Phi);
    SetLength(Result, AnyPhi(Phi));
    for G := 2 to Phi do
    begin
        IsCorrect := True;
        I := Low(Factors);
        while IsCorrect and (I <= High(Factors)) do
        begin
            IsCorrect := IsCorrect and (FastExp(G, Phi div Factors[I], p) <> 1);
            Inc(I);
        end;
        if IsCorrect then
        begin
            Result[Count] := G;
            Inc(Count);
        end;
    end;

    //
//    SetLength(Result, Count);
end;

function IsPrime(N: Integer): Boolean;
var
    I: Integer;
begin
    Result := True;
    I := 2;
    while Result and (I < Trunc(Sqrt(N))) do
    begin
        Result := Result and (N mod I <> 0);
        Inc(I);
    end;
end;

function GCD(A, B: Integer): Integer;
begin
    if B = 0 then
        Result := A
    else
        Result := GCD(B, A mod B);
end;

function IsRelativelyPrime(A, B: Integer): Boolean;
begin
    Result := GCD(A, B) = 1;
end;

var
  a: TIntArray;I: Integer;

begin
writeln(IsPrime(17));

  a := FindPrimitiveRoots(115249);
//  SetLength(a, 0);
//Writeln(AnyPhi(17*3));
//a:=Factorize(911);
//  a := FindPrimitiveRoots(911);
  writeln('Number of primitives ', Length(a));
  for I := 0 to 500 do
    Write(a[I], ' ');
Readln;
end.