Diagon Alley

Some discussion of the nature of proof; listing rationals between 0 and 1; function vs. algorithm; question whether any list of irrationals is possible; Cantor's diagonalization proof that it isn't; discussion about 1-many correspondence between rationals and reals; approach to the idea that the power set of an infinite set is a higher order of infinity because you could do the diagonalization proof on binary expansions between 0 and 1, leading to the construction 2^n numbers not in the original set.  I am interested in what computer scientists make of the discussion we (Kenneth Foner and I in particular) had (and which I am not pretty but not fully confident about) concerning the difference between a function that picks out all primes (which would allow you to use the Sieve of Eratosthenes efficiently, in, um polynomial time [right?], and which we can't [right?]) and an algorithm which ultimately has to do it through a somewhat stream-lined brute force procedure.