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.
fn jacobi(aa u64, na u64) ?int {
    mut a := aa
    mut n := na
    if n%2 == 0 {
        return error("'n' must be a positive odd integer")
    }
    a %= n
    mut result := 1
    for a != 0 {
        for a%2 == 0 {
            a /= 2
            nn := n % 8
            if nn == 3 || nn == 5 {
                result = -result
            }
        }
        a, n = n, a
        if a%4 == 3 && n%4 == 3 {
            result = -result
        }
        a %= n
    }
    if n == 1 {
        return result
    }
    return 0
}
 
fn main() {
    println("Using hand-coded version:")
    println("n/a  0  1  2  3  4  5  6  7  8  9")
    println("---------------------------------")
    for n := u64(1); n <= 17; n += 2 {
        print("${n:2} ")
        for a := u64(0); a <= 9; a++ {
            t := jacobi(a, n)?
            print(" ${t:2}")
        }
        println('')
    }
}
 