I&#x27;d like to draw attention to a fact already pointed out by Chinjut in this thread: The original formulation of Euclid&#x27;s proof is in fact entirely constructive, contrary to what the article claims.<p>Michael Hardy and Catherine Woodgold have written a very nice and readable account on the misconceptions about Euclid&#x27;s proof (published in 2009). I&#x27;m sorry that I can only give a paywalled link; at least the first two pages are available. <a href="http:&#x2F;&#x2F;link.springer.com&#x2F;article&#x2F;10.1007%2Fs00283-009-9064-8" rel="nofollow">http:&#x2F;&#x2F;link.springer.com&#x2F;article&#x2F;10.1007%2Fs00283-009-9064-8</a><p>Incidentally, with the specific situation at hand, the question &quot;constructive vs. nonconstructive&quot; is slightly moot. This is because there is a certain metatheorem in mathematical logic which states: If there is a nonconstructive proof of a statement, then there is also a constructive proof.<p>Of course this metatheorem doesn&#x27;t apply to arbitrary statements, only to statements of a specific logical form (so called &quot;geometric sequents&quot;). But the statement &quot;there are infinitely many prime numbers&quot; can be put into such a form. Also, in case you are wondering, this metatheorem admits itself a constructive proof.<p>Summarizing, there is a mechanical way to turn any nonconstructive proof of the infinitude of the primes into a constructive one.<p>The key words to look up here are &quot;double-negation translation&quot; and &quot;Friedman&#x27;s trick&quot;. Fantastically, the double-negation translation turns out to be &quot;the same as&quot; the continuation-passing style transformation, if viewed from the right angle. Some pointers are in this slide deck: <a href="http:&#x2F;&#x2F;rawgit.com&#x2F;iblech&#x2F;talk-constructive-mathematics&#x2F;master&#x2F;negneg-translation.pdf" rel="nofollow">http:&#x2F;&#x2F;rawgit.com&#x2F;iblech&#x2F;talk-constructive-mathematics&#x2F;maste...</a>