ℕ

Prime Numbers

Middle School

Definition

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Every natural number can be uniquely expressed as a product of primes.

Formulas

π(x) ∼ (x)/(ln x)

Prime counting function estimate (Prime Number Theorem)

Examples

Example 1

List all primes up to 100.

Example 2

Is 91 prime?

History

Discovered by: Euclid (c. 300 BCE)

Euclid proved there are infinitely many primes. This is one of the most elegant proofs in history.

Applications

Cryptography

Foundation of RSA

Hash Functions

Collision avoidance

Random Numbers

Linear congruential generators