' AKS test for primes
DECLARE SUB PascalTriangle (N%, PasTri&())
DECLARE FUNCTION IsPrime% (N%)
DECLARE SUB ExpandPoly (N%)
CONST PASTRILAST% = 33 ' for 32-bit integer type
CONST TRUE% = -1, FALSE% = 0
FOR N% = 0 TO 9
  CALL ExpandPoly(N%)
NEXT N%
FOR N% = 2 TO PASTRILAST%
  IF IsPrime%(N%) THEN PRINT USING "###"; N%;
NEXT N%
PRINT
END

SUB ExpandPoly (N%)
  DIM VZ$(0 TO 1)
  VZ$(0) = "+"
  VZ$(1) = "-"
  DIM PasTri&(0 TO PASTRILAST%)
  IF N% > PASTRILAST% THEN
    PRINT N%; "is out of range"
    STOP
  END IF
  SELECT CASE N%
    CASE 0
      PRINT "(x - 1) ^ 0 = 1"
    CASE 1
      PRINT "(x - 1) ^ 1 = x - 1"
    CASE ELSE
      CALL PascalTriangle(N%, PasTri&())
      PRINT "(x - 1) ^"; N%; " = x ^"; N%;
      BVZ% = 1
      FOR J% = N% - 1 TO N% \ 2 + 1 STEP -1
        PRINT VZ$(BVZ%); PasTri&(N% - J%); "* x ^"; J%;
        BVZ% = ABS(1 - BVZ%)
      NEXT J%
      FOR J% = N% \ 2 TO 2 STEP -1
        PRINT VZ$(BVZ%); PasTri&(J%); "* x ^"; J%;
        BVZ% = ABS(1 - BVZ%)
      NEXT J%
      PRINT VZ$(BVZ%); PasTri&(1); "* x ";
      BVZ% = ABS(1 - BVZ%)
      PRINT VZ$(BVZ%); PasTri&(0)
  END SELECT
END SUB

FUNCTION IsPrime% (N%)
  DIM PasTri&(0 TO PASTRILAST%)
  IF N% > PASTRILAST% THEN
    PRINT N%; "is out of range"
    STOP
  END IF
  CALL PascalTriangle(N%, PasTri&())
  Res% = TRUE%
  I% = N% \ 2
  DO WHILE Res% AND (I% > 1)
    Res% = Res% AND (PasTri&(I%) MOD N% = 0)
    I% = I% - 1
  LOOP
  IsPrime% = Res%
END FUNCTION

SUB PascalTriangle (N%, PasTri&())
  ' Calculate the N'th line 0.. middle
  PasTri&(0) = 1
  J% = 1
  DO WHILE J% <= N%
    J% = J% + 1
    K% = J% \ 2
    PasTri&(K%) = PasTri&(K% - 1)
    FOR K% = K% TO 1 STEP -1
      PasTri&(K%) = PasTri&(K%) + PasTri&(K% - 1)
    NEXT K%
  LOOP
END SUB