Prime Numbers: Complete Guide
Definition: A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
In other words, a number is prime if it has exactly two factors: 1 and itself.
Basic Properties of Prime Numbers
- 2 is the smallest prime number and the only even prime number.
- Every prime number greater than 2 is odd.
- There are infinitely many prime numbers.
- 1 is not a prime number as it has only one factor (itself).
- Composite numbers are numbers that have more than two factors.
Examples of Prime Numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...
Examples of Composite Numbers: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20...
How to Check if a Number is Prime
Method 1: Trial Division
Check if the number is divisible by any integer from 2 to the square root of the number.
Example: Is 17 a prime number?
Square root of 17 ≈ 4.12
Check if 17 is divisible by numbers from 2 to 4:
- 17 ÷ 2 = 8.5 (not divisible)
- 17 ÷ 3 = 5.67 (not divisible)
- 17 ÷ 4 = 4.25 (not divisible)
Since 17 is not divisible by any number from 2 to 4, it is a prime number.
Method 2: Sieve of Eratosthenes
An ancient algorithm to find all prime numbers up to a specified limit.
- Create a list of consecutive integers from 2 to the limit, n.
- Let p = 2, the smallest prime number.
- Mark all multiples of p (p×p, p×(p+1), p×(p+2), etc.) up to n as composite.
- Find the smallest number greater than p that is not marked. This is the next prime number.
- Repeat steps 3 and 4 until p² > n.
- All unmarked numbers are prime.
Prime Number Finder
Important Theorems About Prime Numbers
Fundamental Theorem of Arithmetic
Every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors.
Example:
- 12 = 2² × 3
- 60 = 2² × 3 × 5
- 100 = 2² × 5²
- 17 = 17 (already prime)
Euclid's Theorem: Infinity of Primes
There are infinitely many prime numbers. This was proven by Euclid around 300 BCE.
Proof Outline: Assume there are finitely many primes p₁, p₂, ..., pₙ. Consider N = (p₁ × p₂ × ... × pₙ) + 1. N is either prime or has a prime divisor. If N is prime, then we have found a prime not in our finite list. If N has a prime divisor q, then q cannot be any of p₁, p₂, ..., pₙ (because dividing N by any of these leaves a remainder of 1). Either way, we have found a prime not in our original list, contradicting our assumption.
Prime Number Theorem
The Prime Number Theorem describes the asymptotic distribution of prime numbers. It states that the number of primes less than or equal to n, denoted by π(n), is approximately n/ln(n) for large values of n.
This means that the probability that a randomly chosen number near n is prime is approximately 1/ln(n).
For example, among the numbers near 10,000, about 1 in ln(10,000) ≈ 9.21 is prime.
Applications of Prime Numbers
- Cryptography: RSA encryption algorithm uses the product of two large prime numbers.
- Hash Functions: Prime numbers are used in hash tables and hash functions.
- Random Number Generation: Prime numbers help in generating random numbers.
- Clock Arithmetic: Used in modular arithmetic and number theory.
Special Types of Prime Numbers
| Type | Description | Examples |
|---|---|---|
| Twin Primes | Pairs of primes that differ by 2 | (3,5), (5,7), (11,13), (17,19) |
| Mersenne Primes | Primes of the form 2ⁿ-1 | 3, 7, 31, 127 (for n=2,3,5,7) |
| Fermat Primes | Primes of the form 2²ⁿ+1 | 3, 5, 17, 257, 65537 |
| Sophie Germain Primes | Primes p where 2p+1 is also prime | 2, 3, 5, 11, 23, 29, 41, 53 |
Programming Implementations
Checking if a Number is Prime
Sieve of Eratosthenes Implementation
Prime Factorization
Prime Numbers Quiz
1. Which of the following is NOT a prime number?
2. What is the only even prime number?
3. What is the prime factorization of 60?
4. Using the Sieve of Eratosthenes to find all primes up to 20, which number is crossed out first?
5. What is the 10th prime number?