1

I'm not very proficient with math, but Ive managed to make my way to problem 7 of Project Euler using python. I have to now find the 10,001st prime number. I'm reading about Eucilid's theorem. But I'm afraid I do not understand enough about mathematical notation to understand the theorem.

What do the numbers in the p=p1,p2,p3 expression on this page (http://en.wikipedia.org/wiki/Euclid%27s_theorem#Euclid.27s_proof) mean? Is p the prime number? and the 1,2,3,4 are just counting the position?

Thanks in advance for your help.

Kelbizzle
  • 113

2 Answers2

3

To turn this into the language of a programmer, $p$ is essentially an array of prime numbers. So $p_1$ is the first element of the array, $p_2$ is the second, and so on.

lemon
  • 3,548
  • I am not sure what OP is talking about but its not possible to find 10001 st prime without computers right ? – Rene Schipperus Jul 06 '14 at 16:32
  • 1
    @ReneSchipperus Generally speaking, you are correct, there is no formula for the $n$-th prime (if you were to figure one out then you'd win every prize in mathematics). – lemon Jul 06 '14 at 16:34
  • @ReneSchipperus OF course this is possible without computer. I'm pretty sure some the "old ones" listed all primes up to several millions. After all they also computed $30§ decimals of $\pi$ by hand or manually divised a method to construct the regular $257$-gon with straightedge and compasses. – Hagen von Eitzen Jul 06 '14 at 16:38
  • https://projecteuler.net/problem=7 I'm trying to use a computer :-) – Kelbizzle Jul 06 '14 at 16:38
  • @HagenvonEitzen I don't think he was specifically interested in the 10001st prime, he meant for an arbitrary number. – lemon Jul 06 '14 at 16:39
  • @Kelbizzle if you want a hint then look up the Sieve of Eratosthenes. – lemon Jul 06 '14 at 16:41
  • @user2584283 Thank you, I've head of that. I will check that out now. Thanks again everyone for your help. – Kelbizzle Jul 06 '14 at 16:43
  • What I meant was that I alone sitting at by desk, maybe with a pocket calculator, would not be able to calculate the 10001 prime without prohibitively difficult work. I mean there is no clever way using prime number theorem or something else. – Rene Schipperus Jul 06 '14 at 16:52
1

Yes indeed, that's the prime number position. Euler's proof of the infinitude of primes is a proof by contradiction, which assumes that the primes can be ordered into a finite set. Then, Euclid builds a number, which is the finite product of all primes. Then he adds 1 to that number, and he discovers that he has just built another prime.

Daniel Charry
  • 345