Siteadmin, Check users, nsTeam1RO, nsTeam1RW, nsTeam1_talkRO, nsTeam1_talkRW, oversight, Administrators
30,650
edits
Changes
move up simpler, more basic info
A '''prime number''' is a [[natural number]] that is divisible by only 1 and itself. The only even prime number is 2. There is no upper limit to the quantity of primes, but there is no known formula for deriving the nth prime. [[Leonhard Euler]] once commented: <blockquote>
A '''prime number''' is a [[natural number]] that is divisible by only 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13...
[[Leonhard Euler]] wrote: <blockquote>
''Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate.''
''Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate.''
</blockquote>
</blockquote>
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 first few prime numbers are 2, 3, 5, 7, 11, 13...
==Sieve of Eratosthenes==
To construct a table of all prime numbers less than ''n'', you would use a method called the [[Sieve of Eratosthenes]]. Simply write down an ordered list of all counting numbers greater than 1. Beginning with 2*2 = 4, cross out every second number:
To construct a table of all prime numbers less than ''n'', you can use a method called the [[Sieve of Eratosthenes]]. Simply write down an ordered list of all counting numbers greater than 1. Beginning with 2*2 = 4, cross out every second number:
:2 3 <s>4</s> 5 <s>6</s> 7 <s>8</s> 9 <s>10</s> 11 ...
:2 3 <s>4</s> 5 <s>6</s> 7 <s>8</s> 9 <s>10</s> 11 ...
Beginning with 5*5 = 25, cross out every fifth number, then repeat for the primes 7, 11, 13, etc. until <math>\sqrt{n}</math>.
Beginning with 5*5 = 25, cross out every fifth number, then repeat for the primes 7, 11, 13, etc. until <math>\sqrt{n}</math>.
The number of primes smaller than a given number <math>N</math> is roughly <math>\frac{N}{\ln(N)}</math>, where <math>\ln(N)</math> is the [[natural logarithm]] (base ''[[e]]'') of <math>N</math>.<ref>http://home.att.net/~numericana/answer/primes.htm</ref> This is a formulation of a more general statement known as the [[prime number theorem]].
==The Prime Numbers==
{{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.
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)):
<math>\sum_{p\le x}p^{-1}\approx\log\log x</math>
==Alternative Definition==
==Alternative Definition==