Changes

There is no upper limit to the quantity of primes, but there is no known formula for deriving the nth prime.  

There is no upper limit to the quantity of primes, but there is no known formula for deriving the nth prime.  

The only even prime number is 2.   

The only [[even]] prime number is 2.   

==Sieve of Eratosthenes==

==Sieve of Eratosthenes==

{{main|Prime Number Theorem}}

{{main|Prime Number Theorem}}

It is easy to prove that there are an infinite number of primes using Euclid's second theorem:  Imagine there is a finite set consisting of all the primes.  Multiply them all together, add 1, and call this N.  N would not be divisible by any number in the set--there would always be a remainder of 1.  Because all non-prime numbers can be decomposed into a product of underlying primes, N must be divisible by some prime not in the set (possibly itself), thus contradicting the assumption that the set contained all of the primes.

It is easy to prove that there are an infinite number of primes using Euclid's second theorem:  Imagine there is a finite set consisting of all the primes.  Multiply them all together, add 1, and call this N.  N would not be divisible by any number in the set--there would always be a remainder of 1.  Because all non-prime numbers can be decomposed into a product of underlying primes (by the [[Fundamental Theorem of Arithmetic]]), N must be divisible by some prime not in the set (possibly itself), thus contradicting the assumption that the set contained all of the primes.

Another proof that there are infinitely many primes shows something stronger, namely the sum of the reciprocals of primes less than n "grows like" log(log(n)):

Another proof that there are infinitely many primes shows something stronger, namely the sum of the reciprocals of primes less than n "grows like" log(log(n)):

==Cryptography==

==Cryptography==

The security of [[public-key cryptography]] schemes such as [[RSA]] depend on the difficulty of prime factorization, if a pattern in the distribution of prime numbers is discovered, then such cryptographic schemes could become vulnerable to attack.

The security of [[public-key cryptography]] schemes such as [[RSA]] depend on the difficulty of prime factorization, if a pattern in the distribution of prime numbers is discovered, then such [[cryptographic]] schemes could become vulnerable to attack.

==References==

==References==

* [[Composite number]]

* [[Composite number]]

==External Links==

==External Links==

:[http://www.mersenne.org/ ''Great Internet Mersenne Prime Search'' project website]

:[http://www.mersenne.org/ ''Great Internet Mersenne Prime Search'' project website]

:[http://primes.utm.edu/ Prime Number resource Archieve]

:[http://primes.utm.edu/ Prime Number resource Archive]

[[Category:Number Theory]]

[[Category:Number Theory]]