On the Subject of the Legendre Symbol

If you thought this was bad, wait until you find out about the generalization of this...

Let A be the top number and P be the bottom number

If A^((P-1)/2) mod P = 1 then press R, else press N.

Tip: Use modular exponentiation, or a beefy calculator.