Prime number

Primes-vs-composites

Prime number Cuisenaire rods 7

Rhind Mathematical Papyrus

Prime-counting relative error

Ulam 2

Error creating thumbnail:

Riemann zeta function absolute value

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A prime number is a fundamental concept in number theory and has been studied for thousands of years. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.

Properties

Prime numbers have several important properties:

• They are the building blocks of the integers, as every integer greater than 1 can be uniquely factored into prime numbers, a concept known as the fundamental theorem of arithmetic.
• The number 2 is the only even prime number, as all other even numbers can be divided by 2.
• There are infinitely many prime numbers, a fact that was first proven by the ancient Greek mathematician Euclid.

Distribution

The distribution of prime numbers among the integers is a central topic in number theory. The prime number theorem describes the asymptotic distribution of prime numbers and states that the number of primes less than a given number \( n \) is approximately \( \frac{n}{\ln(n)} \).

Prime Number Tests

Several algorithms exist to test whether a number is prime:

• Trial division: The simplest method, which involves dividing the number by all integers up to its square root.
• Sieve of Eratosthenes: An ancient algorithm that efficiently finds all primes up to a given limit.
• Miller-Rabin primality test: A probabilistic test that can quickly determine if a number is likely prime.

Applications

Prime numbers have numerous applications in modern cryptography, particularly in public-key cryptography algorithms such as RSA.

Related Concepts

• Composite number
• Twin prime
• Mersenne prime
• Fermat prime
• Goldbach's conjecture
• Prime gap
• Prime factorization

See Also

• List of prime numbers
• Prime number theorem
• Euclid's theorem
• Riemann hypothesis
• Sieve of Atkin
• Sophie Germain prime