Identifying Primes and Trial Division
What you'll learn: You'll master a systematic method to determine whether any given number is prime by testing divisibility only up to its square root.
The Core Idea
A prime number has exactly two divisors: 1 and itself. To verify primality, we could test divisibility by every integer from 2 up to n - 1, but that's inefficient. Here's the key insight: if a number n has a divisor greater than √n, it must also have a corresponding divisor smaller than √n.
Why? Because divisors come in pairs. If n = a × b and a > √n, then b must be less than √n (otherwise a × b would exceed n). So we only need to check potential divisors up to √n.
Trial Division Method
Step 1: Check if n ≤ 1. If so, it's not prime.
Step 2: Check if n = 2. If so, it's prime (the only even prime).
Step 3: Check if n is even. If so, it's not prime.
Step 4: Test divisibility by all odd numbers from 3 up to √n. If any divides n evenly, then n is composite. If none do, n is prime.
Example
Is 97 prime?
- √97 ≈ 9.85, so test divisors up to 9
- Test 3: 97 ÷ 3 = 32 remainder 1 ✗
- Test 5: 97 ÷ 5 = 19 remainder 2 ✗
- Test 7: 97 ÷ 7 = 13 remainder 6 ✗
- Test 9: 97 ÷ 9 = 10 remainder 7 ✗
Since no divisor worked, 97 is prime.
Key Takeaway: Trial division tests primality efficiently by checking divisibility only up to √n, leveraging the fact that divisors come in pairs split by the square root.