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
<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 +--------------------------------------+
>
More information about the Python-list
mailing list