Prime Number Detective & Factor Finder

A prime number is any whole number strictly greater than 1 that cannot be formed by multiplying two smaller positive integers. In rigorous terms, an integer p > 1 is prime if and only if its only positive divisors are 1 and p.

Examples of Primes: 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...

A common misconception in mathematics is that 1 is prime. However, mathematicians deliberately define primes as numbers with exactly two distinct positive divisors.

• Number 7: Divisors are 1 and 7 (exactly 2 distinct divisors → Prime).
• Number 6: Divisors are 1, 2, 3, 6 (4 distinct divisors → Composite).
• Number 1: Divisor is 1 only (only 1 divisor → Neither Prime nor Composite).

If 1 were considered prime, the Fundamental Theorem of Arithmetic would break down because numbers would have infinite prime factorizations (e.g. 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3...).

Every integer greater than 1 can be represented as a product of prime numbers in exactly one unique way (up to the order of the factors). This is why primes are called the atoms of number theory.

Canonical Prime Factorization: N = p₁^a₁ × p₂^a₂ × ... × p_k^a_k
Example: 360 = 2³ × 3² × 5
Example: 1,024 = 2¹⁰
Example: 997 = 997¹ (Prime)

Created by the ancient Greek polymath Eratosthenes of Cyrene (276–194 BC), the Sieve is an extraordinarily fast algorithm for generating all prime numbers up to an upper limit N.

1. Write down all consecutive numbers from 2 up to N.
2. Start with the smallest prime, p = 2.
3. Cross off all multiples of 2 greater than 2 (4, 6, 8, 10, 12...).
4. Move to the next uncrossed number, which is 3. Cross off all multiples of 3 (9, 15, 21... multiples already crossed by 2 can be skipped).
5. Repeat for the next uncrossed numbers (5, 7, 11...).
6. Stop when p² > N. All remaining uncrossed numbers are guaranteed to be prime!

To test if a number N is prime by trial division, you do not need to divide by every number up to N. You only need to test prime divisors up to √N.

Example: To test if 997 is prime:
√997 ≈ 31.57
Primes to test: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.
None of these divide 997 evenly → 997 is 100% Prime!

Decade Range	Count	List of Prime Numbers
1 – 10	4	2, 3, 5, 7
11 – 20	4	11, 13, 17, 19
21 – 30	2	23, 29
31 – 40	2	31, 37
41 – 50	3	41, 43, 47
51 – 60	2	53, 59
61 – 70	2	61, 67
71 – 80	3	71, 73, 79
81 – 90	2	83, 89
91 – 100	1	97
Total 1 – 100	25 Primes	25% of the first 100 numbers are prime

• RSA Public-Key Cryptography: Protects banking, credit card transactions, HTTPS web traffic, and cryptocurrency wallets. It relies on the extreme difficulty of factoring the product of two 300-digit prime numbers.
• Hashing & Hash Tables: Hash table arrays use prime sizes to avoid data collisions in computer software and database indexes.
• Cicada Biological Cycles: Periodical cicadas emerge every 13 or 17 years (both prime numbers) to avoid coinciding with predator reproductive life cycles.
• Pseudorandom Number Generators: Linear congruential algorithms use massive Mersenne primes (e.g. 231 − 1) to generate unpredictable sequences.