Bill's post on how to derive the non-finiteness of the primes from Van der Waerden's theorem reminds me of a nice proof using Kolmogorov complexity.
A quick primer: Fixed some universal programming language. Let C(x), the Kolmogorov complexity of x, be the length of the smallest program that outputs x. One can show by a simple counting argument for every n there is an x such that C(x) ≥ n. We call such x "random".
Suppose we had a finite list of primes p1…pk. Then any number m can be expressed as p1e1···pkek. Pick n large, a random x of length n and let m be the number x expresses in binary. We can compute m from e1,…,ek and a constant amount of other information, remembering that k is a constant. Each ei is at most log m and so we can describe all of them in O(log log m) bits and thus C(m) = O(log log m). But roughly C(m) = C(x) ≥ n = log m, a contradiction.
But we can do better. Again pick n large, a random x of length n and let m be the number x expresses in binary. Let pi be the largest prime that divides m where pi is the ith prime. We can describe m by pi and m/pi, or by i and m/pi. So we have C(m) ≤ C(i,m/pi) ≤ C(i) + C(m/pi) + 2 log C(pi) ≤ log i + log m/pi + 2 log log i + c. The 2 log C(pi) term is needed to specify the separation between the program for i and the program for m/pi.
Since C(m) ≥ log m, we have
log m ≤ log i + log (m/pi)+ 2 log log i + c
log m ≤ log i + log m - log pi + 2 log log i + c
log pi ≤ log i + 2 log log i + c
pi ≤ O(i (log i)2)
The prime number theorem has pi approximately i log i, so we get just a log factor off from optimal with simple Kolmogorov complexity.
I wrote a short introduction to Kolmogorov complexity with this proof. I originally got the proof from the great text on Kolmogorov complexity from Li and Vitányi and they give credit to Piotr Berman and John Tromp.