Prime Number Checker
Check if a number is prime using efficient algorithms. Learn about prime numbers, their properties, and applications in cryptography and mathematics.
Check if Number is Prime
Enter a positive integer to check if it's a prime number:
Examples: 2, 3, 5, 7, 11, 13, 17, 19...
What is a Prime Number?
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Prime numbers are the building blocks of all other numbers and play a crucial role in number theory and cryptography.
Prime Number Definition
Example: 7 has divisors 1 and 7, so it's prime
Testing Methods
๐งฎ Trial Division
Check divisibility by all numbers up to โn. Simple but can be slow for large numbers.
โก Optimized Trial Division
Skip even numbers and use 6kยฑ1 optimization. Much faster than basic trial division.
๐ Sieve of Eratosthenes
Find all primes up to a limit by eliminating multiples. Best for checking ranges.
First 25 Prime Numbers
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Properties of Prime Numbers
๐ต 2 is Special
2 is the only even prime number and the smallest prime
๐ด Odd Numbers
All primes greater than 2 are odd numbers
๐ Twin Primes
Prime pairs that differ by 2: (3,5), (5,7), (11,13), (17,19)
โก Mersenne Primes
Primes of form 2^p - 1: 3, 7, 31, 127, 8191...
Applications of Prime Numbers
๐ Cryptography
RSA encryption relies on the difficulty of factoring large composite numbers
๐ฒ Random Number Generation
Used in generating secure random numbers for encryption
๐งฎ Number Theory
Fundamental theorem of arithmetic: every integer > 1 is prime or product of primes
๐ต Music Theory
Prime numbers help create rhythmic patterns and musical scales
The Prime Number Theorem
The prime number theorem describes the distribution of prime numbers among positive integers. It states that the number of primes less than or equal to n is approximately n/ln(n).
where ฯ(n) is the number of primes โค n
Largest Known Prime Numbers
| Type | Digits | Year Discovered |
|---|---|---|
| Mersenne Prime | 24,862,048 | 2018 |
| General Prime | 23,249,425 | 2016 |
| Fermat Prime | 6,542,211 | 1953 |
Prime Number Conjectures
๐ฏ Goldbach Conjecture
Every even integer greater than 2 can be expressed as sum of two primes
โพ๏ธ Twin Prime Conjecture
There are infinitely many twin prime pairs
๐ Riemann Hypothesis
About the zeros of the Riemann zeta function
๐ก Fun Fact: The largest known prime number has over 24 million digits! Prime numbers are discovered using distributed computing projects like GIMPS (Great Internet Mersenne Prime Search).
Prime Number Testing Algorithms
- Trial Division: Check divisibility by all integers up to โn
- Sieve of Eratosthenes: Find all primes up to a limit by elimination
- Miller-Rabin: Probabilistic primality test for large numbers
- AKS Algorithm: Deterministic polynomial-time primality test
Prime Factorization
Every composite number can be expressed as a product of prime numbers. This is called the fundamental theorem of arithmetic.
Examples:
| Number | Prime Factors | Factorization |
|---|---|---|
| 12 | 2, 3 | 2ยฒ ร 3 |
| 24 | 2, 3 | 2ยณ ร 3 |
| 30 | 2, 3, 5 | 2 ร 3 ร 5 |
| 60 | 2, 3, 5 | 2ยฒ ร 3 ร 5 |