Prime Number Formulas
Explore mathematical formulas and algorithms for prime numbers, from basic primality testing to advanced number theory concepts and efficient prime generation methods.
1Prime Number Definition
A prime number is a natural number greater than 1 with exactly two positive divisors.
In Simple Terms:
A number p is prime if:
- • p > 1
- • p has no divisors other than 1 and p
Examples:
Prime: 2, 3, 5, 7, 11, 13, 17, 19, 23...
Not Prime: 1, 4, 6, 8, 9, 10, 12, 14, 15...
2Basic Primality Test
The fundamental method to test if a number n is prime by checking divisibility.
Algorithm Steps:
- 1. If n < 2, return false
- 2. If n = 2, return true
- 3. If n is even, return false
- 4. Check odd divisors up to √n
Time Complexity:
3Prime Counting Function
The function π(x) counts the number of prime numbers less than or equal to x.
Examples:
Prime Number Theorem:
Asymptotic approximation for large x
4Sieve of Eratosthenes
An efficient algorithm to find all prime numbers up to a given limit n.
Algorithm:
1. Create list of consecutive integers from 2 to n
2. Start with the first number (2)
3. Mark all multiples of this number (except itself)
4. Find next unmarked number and repeat
5. Continue until processed all numbers ≤ √n
Time Complexity:
Space Complexity:
5Wilson's Theorem
A theorem that provides a necessary and sufficient condition for primality.
Example (p = 5):
So 5 is prime ✓
Note:
While theoretically important, this test is impractical for large numbers due to the factorial computation.
6Fermat's Little Theorem
A fundamental theorem used in primality testing and cryptography.
Primality Test:
If the converse fails, n is definitely composite:
Application:
Used in Miller-Rabin primality test and RSA cryptography. Base for pseudoprime concepts.
7Mersenne Primes
Special primes of the form 2ᵖ - 1 where p is prime.
Examples:
Lucas-Lehmer Test:
Efficient test specifically for Mersenne primes, used to find the largest known primes.