I don't really agree that the primes “have a very simple definition” in that the notion of ‘primeness’ is one of satisfiability and no constructive algorithm is known to exist.

I'm not sure what you mean by not having a constructive algorithm to produce primes. The Sieve of Eratosthenes will output any given prime, with the primes coming out in order, given enough time. There may not be an efficient algorithm, but for most definitions of "information" that won't matter. The sequence of all primes is both so richly structured we've probably only scratched the surface and almost entirely bereft of information.

Yup you're right and I'm wrong.

I'm not sure what you're getting at here. Is it not relevant that there is a simple algorithm to enumerate the primes, or, even more so, determine whether a given value is prime?

Of course it's relevant. qubex is just confused.