[sweezyjeezy]

The article starts by saying mathematicians want things to work for large numbers, but that doesn't really get to the crux of the issue with primes. Infinite sequences are ubiquitous in number theory, and in general it will be infeasible to have a test for inclusion in these sequences for large enough numbers. But often they have structure that we can use to characterise them very precisely - think about square numbers, it's easy to say what the trillionth square number is, what it's remainder when you divide by 13, etc.

What makes primes hard, and also interesting, is that they seem to be extremely unstructured, we believe they behave like a kind of random number generator, even though they are clearly not random. In fact many of the theorems and conjectures mentioned in the article actually hinge on this. Random numbers are unpredictable on a small scale, but on a large scale they have very nice distributional properties, whereas more structured ones of similar growth rate will often have undesirable restrictions on them.