Calculation of prime numbers - why so difficult? As I read more and more about advanced mathematics, the more complex and obscure topics seem to be tougher to bend the rules of math to describe. However, the simple (and undoubtedly very useful) subject of prime number identification remains an enigma (to me, at least). For a system with rules so simple, calculation isn't. Even though the rules of the calculation change as larger and larger values are tested, because of additional primes to take into consideration when testing a given value, how is there not a computationally cheap and easy way of identifying primes? I've got pages and pages full of attempts to find patterns (with a knowledge base not too well suited for this sort of research), and as soon as I have a large enough value that I'm testing, the pattern falls apart in quite an ugly manner.

Depends on what you call "cheap and easy". Adleman-Pomerance-Rumely-Cohen-Lenstra and Elliptic Curve Primality testing have been used to prove primality of numbers (not of special form) with thousands of digits. 
