PROGRAM "akstest"
' AKS test for primes

DECLARE FUNCTION Entry ()
INTERNAL FUNCTION ExpandPoly(n@@)
INTERNAL FUNCTION PascalTriangle(n@@, @pasTri&&[])
INTERNAL FUNCTION IsPrime(n@@)
INTERNAL FUNCTION Vz$(b@)
$$PasTriMax = 33 ' for 32-bit integer type

FUNCTION Entry()
  FOR n@@ = 0 TO 9
    ExpandPoly(n@@)
  NEXT
  FOR n@@ = 2 TO $$PasTriMax
    IF IsPrime(n@@) THEN PRINT FORMAT$("###", n@@);
  NEXT
  PRINT
END FUNCTION

FUNCTION ExpandPoly(n@@)
  DIM pasTri&&[$$PasTriMax]
  IF n@@ > $$PasTriMax THEN
    PRINT n@@; " is out of range"
    QUIT(1)
  END IF
  SELECT CASE n@@
    CASE 0:
      PRINT "(x - 1) ^ 0 = 1"
    CASE 1:
      PRINT "(x - 1) ^ 1 = x - 1"
    CASE ELSE:
      PascalTriangle(n@@, @pasTri&&[])
      PRINT "(x - 1) ^"; n@@; " = x ^"; n@@;
      bVz@ = $$TRUE
      FOR j@@ = n@@ - 1 TO n@@ \ 2 + 1 STEP -1
        PRINT " "; Vz$(bVz@); pasTri&&[n@@ - j@@]; " * x ^"; j@@;
        bVz@ = NOT bVz@
      NEXT
      FOR j@@ = n@@ \ 2 TO 2 STEP -1
        PRINT " "; Vz$(bVz@); pasTri&&[j@@]; " * x ^"; j@@;
        bVz@ = NOT bVz@
      NEXT
      PRINT " "; Vz$(bVz@); pasTri&&[1]; " * x ";
      bVz@ = NOT bVz@
      PRINT Vz$(bVz@); pasTri&&[0]
  END SELECT

END FUNCTION

FUNCTION PascalTriangle(n@@, @pasTri&&[])
' Calculate the n@@'th line 0.. middle
  pasTri&&[0] = 1
  j@@ = 1
  DO WHILE j@@ <= n@@
    INC j@@
    k@@ = j@@ \ 2
    pasTri&&[k@@] = pasTri&&[k@@ - 1]
    FOR k@@ = k@@ TO 1 STEP -1
      pasTri&&[k@@] = pasTri&&[k@@] + pasTri&&[k@@ - 1]
    NEXT
  LOOP
END FUNCTION

FUNCTION IsPrime(n@@)
  DIM pasTri&&[$$PasTriMax]
  IF n@@ > $$PasTriMax THEN
    PRINT n@@; " is out of range"
    QUIT(1)
  END IF
  PascalTriangle(n@@, @pasTri&&[])
  res@ = $$TRUE
  i@@ = n@@ \ 2
  DO WHILE res@ AND (i@@ > 1)
    res@ = res@ AND (pasTri&&[i@@] MOD n@@ = 0)
    DEC i@@
  LOOP
  RETURN res@
END FUNCTION

FUNCTION Vz$(b@)
  IF b@ THEN RETURN "-" ELSE RETURN "+"
END FUNCTION
END PROGRAM