If you are interested in learning more about python and caching I wrote a post about it couple days ago:
http://russell.ballestrini.net/explaining-cache-with-python/
http://russell.ballestrini.net/explaining-cache-with-python/
Also, you might want to look into Sieve of Eratosthenes, as you only have to test up to sqrt(n) for primality: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes