In "Meta Math!" Greg Chaitin gives a sketch of a proof of the infinitude of primes based on complexity arguments.
Here I want to give a fuller version of that proof.

The gist of his proof is that if there were only a finite number of primes then as each number can be written as a product of primes (we don't require the uniqueness of the prime factorisation for this just that at least one exists), for some sufficiently large N there are insufficient primes products \le N to provide one for each of the N distinct number in need of one.

Now suppose there are but a finite number of primes p_1, .. , p_M. Then as every number from 1 to N has a prime factorisation we may write for any n \in \{1..N\}:

n = p_1^{k_1}\,p_2^{k_2} .. p_M^{k_M}.

where 0 \le k_i \le \log_{p_i}(N).
Now there are N possibilities for n, but \le \prod_{i=1,..M} \log(N)/ \log(p_i) different prime products less than equal to N. So we have:

N \le \log(N) \prod_{i=1..M} 1/\log(p_i) = K \log(N)

But as \lim_{N \to \infty} N/\log(N) = \infty, this last inequality is for sufficiently large N a contradiction, so there cannot be but a finite number of primes.

RonL - There appears to be something wrong with our b****y LaTeX today Chatfield