You don't need to check even numbers for primality. Return false if (n%2 == 0). Take that even further and check all the small factors.

Next up you will probably want to run Fermat's little...