Predicting if $n^2 + 1$ is prime I'm trying to write a program that can tell if $n^2+1$ is prime where n is in the natural numbers (sorry I don't know how to write this in proper math notation). Sure, I can take a brute force approach to check if the number is prime, but I want to check millions of values of n, so as n gets big, $n^2$ gets out of hand quickly and my computing slows down. Is there some more efficient approach to check if it's prime?
 A: One very fast probabilistic primality test is the Miller-Rabin test. 
Here is a working online example of the Miller-Rabin test that would help you appreciate the speed of primality testing using this algorithm.
You can also install PARI/GP and run something like this:
for (n=1,1000000,if(isprime(n^2+1),print(n)))

It's incredibly fast; testing one million values of $n$ takes less than a minute. PARI/GP relies (in part) on the Miller-Rabin test for primality testing.
Note: Under some conditions, the Miller-Rabin test can work as a deterministic primality test (i.e. it will give you a guaranteed answer whether the input number is prime or composite). See e.g. OEIS sequence A014233: smallest odd numbers for which Miller-Rabin test on bases $\le n$-th prime does not reveal compositeness. Essentially, OEIS A014233 gives you a bound below which you can use the Miller-Rabin test deterministically. For example, if you run the test for every prime "base" parameter up to 41, then the test will correctly determine primality of any odd input number up to 3317044064679887385961981.
