Why should I switch to Python? - Infinity of Primes

[David C. Ullrich]

Greg Ewing <greg at cosc.canterbury.ac.nz> wrote in article
<38EAC8C4.ADC25640 at cosc.canterbury.ac.nz>...
> "David C. Ullrich" wrote:
> > 
> >     There's nothing non-constructive about the traditional
> > proof of the infinitude of the sequence of primes - given
> > a sequence of primes it _constructs_ a prime not on the
> > list.
> 
> Um, no it doesn't - it constructs a number which is
> *either* prime *or* divisible by some other prime bigger
> than the one you started with.

	For heaven's sake. Here's a constructive way to find
whether a number is prime: To check whether n is prime
test whether it's divisible by j, for 2 <= j < n.
	Here's a constructive way to find a prime factor
of n: For 2<= k <= n test whether k is prime and then test
whether n is divisible by k.

	I mean really, I didn't mean that the way the proof
is usually _presented_ actually gives that prime. But the
proof contains all the cleverness needed - once we have
that number which is either a larger prime or divisible
by a larger prime then finding the larger prime itself is
trivial. In a perfectly constructive way.
	(Um, actually you should note that the word
"larger" is irrelevant - you inserted the word "bigger".
Given any finite set of primes the construction gives
a prime not in the set.

> If someone actually came up with a formula for constructing
> primes, it would be rather large news -- isn't that one of
> the Big Unsolved Problems?

	I guess you're serious. Finding a "formula" for the
n-th prime is not so easy, but finding an algorithm to
calculate the n-th prime is trivial. (Finding an
_efficient_ algorithm is a different question.)

> -- 
> Greg Ewing, Computer Science Dept,
> +--------------------------------------+
> University of Canterbury,	   | A citizen of NewZealandCorp, a	  |
> Christchurch, New Zealand	   | wholly-owned subsidiary of USA Inc.  |
> greg at cosc.canterbury.ac.nz	   +--------------------------------------+
>