1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you referring to the equation $P = p_1 p_2 \dotsm p_n$ in the first section? $\endgroup$ – epimorphic Jul 6 '14 at 17:08
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am not sure what OP is talking about but its not possible to find 10001 st prime without computers right ? $\endgroup$ – Rene Schipperus Jul 6 '14 at 16:32
  • 1
    $\begingroup$ @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). $\endgroup$ – lemon Jul 6 '14 at 16:34
  • $\begingroup$ @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. $\endgroup$ – Hagen von Eitzen Jul 6 '14 at 16:38
  • $\begingroup$ projecteuler.net/problem=7 I'm trying to use a computer :-) $\endgroup$ – Kelbizzle Jul 6 '14 at 16:38
  • $\begingroup$ @HagenvonEitzen I don't think he was specifically interested in the 10001st prime, he meant for an arbitrary number. $\endgroup$ – lemon Jul 6 '14 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.