# Why should I switch to Python? - Infinity of Primes

David C. Ullrich ullrich at math.okstate.edu
Wed Apr 5 16:44:15 CEST 2000

```Greg Ewing <greg at cosc.canterbury.ac.nz> wrote in article
> "David C. Ullrich" wrote:
> >
> > 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	   +--------------------------------------+
>

```