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.
import Foundation
 
func jacobi(a: Int, n: Int) -> Int {
  var a = a % n
  var n = n
  var res = 1
 
  while a != 0 {
    while a & 1 == 0 {
      a >>= 1
 
      if n % 8 == 3 || n % 8 == 5 {
        res = -res
      }
    }
 
    (a, n) = (n, a)
 
    if a % 4 == 3 && n % 4 == 3 {
      res = -res
    }
 
    a %= n
  }
 
  return n == 1 ? res : 0
}
 
print("n/a  0  1  2  3  4  5  6  7  8  9")
print("---------------------------------")
 
for n in stride(from: 1, through: 17, by: 2) {
  print(String(format: "%2d", n), terminator: "")
 
  for a in 0..<10 {
    print(String(format: " % d", jacobi(a: a, n: n)), terminator: "")
  }
 
  print()
}