119 lines
2.2 KiB
Text
119 lines
2.2 KiB
Text
MODULE AKSTest;
|
|
(* AKS test for primes *)
|
|
|
|
FROM STextIO IMPORT
|
|
WriteLn, WriteString;
|
|
FROM SWholeIO IMPORT
|
|
WriteInt;
|
|
|
|
CONST
|
|
PasTriMax = 33; (* for 32-bit integer type *)
|
|
|
|
TYPE
|
|
TPasTri = ARRAY [0 .. PasTriMax] OF CARDINAL;
|
|
|
|
VAR
|
|
N: CARDINAL;
|
|
|
|
PROCEDURE PascalTriangle(N: CARDINAL; VAR PasTri: TPasTri);
|
|
(* Calculate the N'th line 0.. middle *)
|
|
VAR
|
|
J, K: CARDINAL;
|
|
BEGIN
|
|
PasTri[0] := 1;
|
|
J := 1;
|
|
WHILE J <= N DO
|
|
J := J + 1;
|
|
K := J DIV 2;
|
|
PasTri[K] := PasTri[K - 1];
|
|
FOR K := K TO 1 BY -1 DO
|
|
PasTri[K] := PasTri[K] + PasTri[K - 1];
|
|
END
|
|
END
|
|
END PascalTriangle;
|
|
|
|
PROCEDURE IsPrime(N: CARDINAL): BOOLEAN;
|
|
VAR
|
|
Res : BOOLEAN;
|
|
I : CARDINAL;
|
|
PasTri: TPasTri;
|
|
BEGIN
|
|
IF N > PasTriMax THEN
|
|
WriteInt(N, 1);
|
|
WriteString(" is out of range");
|
|
WriteLn;
|
|
HALT;
|
|
END;
|
|
PascalTriangle(N, PasTri);
|
|
Res := TRUE;
|
|
I := N DIV 2;
|
|
WHILE Res AND (I > 1) DO
|
|
Res := Res AND (PasTri[I] MOD N = 0);
|
|
I := I - 1
|
|
END;
|
|
RETURN Res;
|
|
END IsPrime;
|
|
|
|
PROCEDURE ExpandPoly(N: CARDINAL);
|
|
TYPE
|
|
TVZ = ARRAY BOOLEAN OF CHAR;
|
|
CONST
|
|
VZ = TVZ {'+', '-'};
|
|
VAR
|
|
J : CARDINAL;
|
|
BVZ : BOOLEAN;
|
|
PasTri: TPasTri;
|
|
BEGIN
|
|
IF N > PasTriMax THEN
|
|
WriteInt(N, 1);
|
|
WriteString(" is out of range");
|
|
WriteLn;
|
|
HALT
|
|
END;
|
|
CASE N OF
|
|
| 0:
|
|
WriteString("(x-1)^0 = 1"); WriteLn;
|
|
| 1:
|
|
WriteString("(x-1)^1 = x-1"); WriteLn;
|
|
ELSE
|
|
PascalTriangle(N, PasTri);
|
|
WriteString("(x-1)^");
|
|
WriteInt(N, 1);
|
|
WriteString(" = x^");
|
|
WriteInt(N, 1);
|
|
BVZ := TRUE;
|
|
FOR J := N - 1 TO N DIV 2 + 1 BY -1 DO
|
|
WriteString(VZ[BVZ]);
|
|
WriteInt(PasTri[N - J], 1);
|
|
WriteString("*x^");
|
|
WriteInt(J, 1);
|
|
BVZ := NOT BVZ
|
|
END;
|
|
FOR J := N DIV 2 TO 2 BY -1 DO
|
|
WriteString(VZ[BVZ]);
|
|
WriteInt(PasTri[J], 1);
|
|
WriteString("*x^");
|
|
WriteInt(J, 1);
|
|
BVZ := NOT BVZ
|
|
END;
|
|
WriteString(VZ[BVZ]);
|
|
WriteInt(PasTri[1], 1);
|
|
WriteString("*x");
|
|
BVZ := NOT BVZ;
|
|
WriteString(VZ[BVZ]);
|
|
WriteInt(PasTri[0], 1);
|
|
WriteLn;
|
|
END;
|
|
END ExpandPoly;
|
|
|
|
BEGIN
|
|
FOR N := 0 TO 9 DO
|
|
ExpandPoly(N)
|
|
END;
|
|
FOR N := 2 TO PasTriMax DO
|
|
IF IsPrime(N) THEN
|
|
WriteInt(N, 3)
|
|
END
|
|
END;
|
|
WriteLn;
|
|
END AKSTest.
|