[phaemon]

Euclid's proof isn't a proof by contradiction. As the wikipedia page says:

>"Euclid is often erroneously reported to have proved this result by contradiction"

It simply says that if you are constructing a list of primes, you can always add one more to the list, therefore there are infinitely many.

[tjgq]

The overall structure of the proof is not by contradiction, but one of the steps is. The Wikipedia article calls this out, right after the sentence you quoted.

[lutusp]

Also, even though it's correct that Euclid didn't pose it as a proof by contradiction, it can certainly be posed that way, and I often use that form when presenting it to nonmathematicians.

[tjgq]

Not everyone thinks the same way. There are certainly lay persons out there who do not find proofs by contradiction jarring when they come across them for the first time. I remember I was one of them.

But the impression I get from my (possibly biased) sample is that most non-trained people intuitively see proof by contradiction (or any form of nonconstructive proof, really) as a way of "cheating", because it asserts something does or does not exist without actually producing a (counter)example. YMMV, of course.