Since multiplication distributes over the legendre symbol, it also distributes over the jacobi symbol. That is, [a\n]×[b\n] = [ab\n]. Use this in reverse to write [a\n] as the product of [p\q] for all primes p in a and q in n, including multiplicities.
If the jacobi symbol is split apart, as above, assume there are k primes in a that are 3 mod 4, and l primes in n that are 3 mod 4. Flip the legendre symbols over and follow the quadratic reciprocity law, bringing in kl factors of -1. This is -1 iff kl is odd iff a and n are both 3 mod 4. Therefore quadratic reciprocity is valid for jacobi symbols.
Show that [2,n] and [-1,n] can be evaluated by looking ad n mod 4 and mod 8, as though they were legendre symbols.
One does not need to factor a or n to determine [a\n]. Perform a procedure similar to Euclid's gcd algorithm, keeping ±1 in an accumulator. Divide the bottom into the top, take the remainder, pull out factors of 2 (adjusting the accumulator), and flip (adjusting the accumulator). When the top becomes 1, you are done.
If n happens to be prime (at the start), then the original jacobi symbol [a\n] is itself a legendre symbol. You have computed the legendre symbol, and you know whether a is a square mod n.
Let's have a look at why the relationship fails for composite n. Let n = qk where q is prime and k is even. Let z be a number strictly between 1 and q, and consider [z\n]. This is [z\q] to an even power, and is 1. Now look at the multiplicative group mod n. It is cyclic, hence z is a square iff its discrete log is even. A group homomorphism takes the units mod n onto the units mod p. This effectively reduces the discrete log mod p-1. Subtracting a multiple of an even number from log(z) will not change the parity of log(z). In other words, z is a square mod n iff z is a square mod p. So let z be a nonsquare mod p, and a nonsquare mod n, and the jacobi symbol is not accurate; since it says [z\n] = 1.