The Jacobi symbol is a multiplicative function that generalizes the Legendre symbol. Specifically, the Jacobi symbol (a | n) equals the product of the Legendre symbols (a | p_i)^(k_i), where n = p_1^(k_1)*p_2^(k_2)*...*p_i^(k_i) and the Legendre symbol (a | p) denotes the value of a ^ ((p-1)/2) (mod p)

 (a | p) ≡   1     if a is a square (mod p)
 (a | p) ≡ -1     if a is not a square (mod p)
 (a | p) ≡   0     if a ≡ 0 
If n is prime, then the Jacobi symbol (a | n) equals the Legendre symbol (a | n).

Task

Calculate the Jacobi symbol (a | n).

Reference

 Wikipedia article on Jacobi symbol.
INCLUDE "D2:PRINTF.ACT" ;from the Action! Tool Kit
 
INT FUNC Jacobi(INT a,n)
  INT res,tmp
 
  IF a>=n THEN
    a=a MOD n
  FI
  res=1
  WHILE a
  DO
    WHILE (a&1)=0
    DO
      a=a RSH 1
      tmp=n&7
      IF tmp=3 OR tmp=5 THEN
        res=-res
      FI
    OD
    tmp=a a=n n=tmp
    IF (a%3)=3 AND (n%3)=3 THEN
      res=-res
    FI
    a=a MOD n
  OD
 
  IF n=1 THEN
    RETURN (res)
  FI
RETURN (0)
 
PROC PrintTable(INT maxK,maxN)
  INT res,n,k
  CHAR ARRAY t(10)
 
  Put('n) Put(7) Put('k) Put(124)
  FOR k=0 TO maxK
  DO
    StrI(k,t) PrintF("%3S",t)
  OD
  PutE()
 
  Put(18) Put(18) Put(18) Put(19)
  FOR k=0 TO 3*maxK+2
  DO
    Put(18)
  OD
  PutE()
 
  FOR n=1 TO maxN STEP 2
  DO
    StrI(n,t) PrintF("%3S",t)
    Put(124)
    FOR k=0 TO maxK
    DO
      res=Jacobi(k,n)
      StrI(res,t) PrintF("%3S",t)
    OD
    PutE()
  OD
RETURN
 
PROC Main()
  Put(125) PutE() ;clear the screen
  PrintTable(10,39)
RETURN