How to Test Primes & Factorise — Methods & Tips

Understanding Prime Numbers: The Foundation

A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. The number 2 is the smallest and only even prime; all other primes are odd. The number 1 is not prime—it has only one divisor, and excluding it ensures the Fundamental Theorem of Arithmetic holds: every integer greater than 1 has a unique prime factorisation.

1. Primality Testing: Is This Number Prime?

To determine if a number n is prime, you must check whether it has any divisors other than 1 and itself.

Trial Division: The Manual Method

For small numbers, trial division is straightforward:

1. Check divisibility by 2: If n is even and n ≠ 2, it’s composite.
2. Check odd divisors up to √n: If no divisor ≤ √n divides n, then n is prime.

Why √n? If n = a × b and both a, b > √n, then a × b > n—a contradiction. So at least one factor must be ≤ √n.

Example: Is 97 prime?

• √97 ≈ 9.85
• Check primes ≤ 9: 2, 3, 5, 7
• 97 is not divisible by any → 97 is prime

Example: Is 221 prime?

• √221 ≈ 14.86
• Check primes ≤ 14: 2, 3, 5, 7, 11, 13
• 221 ÷ 13 = 17 → 221 = 13 × 17 (composite)

Optimisations for Manual Testing

• Skip even numbers after 2.
• Use divisibility rules:
  • 3: Sum of digits divisible by 3
  • 5: Ends in 0 or 5
  • 11: Alternating sum of digits divisible by 11

2. Prime Factorisation: Breaking Down Composite Numbers

Every composite number can be expressed as a product of primes. The factor tree method is intuitive and visual.

Step-by-Step Factor Tree

1. Start with the number.
2. Break it into any two factors (not 1 and itself).
3. Continue factoring each composite branch until all leaves are prime.
4. Write the primes in ascending order, using exponents for repeats.

Example: Factorise 504

• 504 = 2 × 252
• 252 = 2 × 126
• 126 = 2 × 63
• 63 = 3 × 21
• 21 = 3 × 7
• 504 = 2³ × 3² × 7

💡 Tip: Always start with the smallest prime factor (2, then 3, etc.) to avoid missing factors.

3. Generating Primes: The Sieve of Eratosthenes

To find all primes up to a limit n, the Sieve of Eratosthenes is efficient and ancient (c. 240 BCE).

Steps:

1. List all integers from 2 to n.
2. Start with the first number (2)—it’s prime.
3. Cross out all multiples of 2 (≥ 4).
4. Move to the next uncrossed number (3)—it’s prime.
5. Cross out all multiples of 3 (≥ 9).
6. Repeat until you reach √n.
7. All remaining uncrossed numbers are prime.

Example: Primes ≤ 30

• After sieving: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

4. Advanced Methods (For Context)

• Miller-Rabin Test: A probabilistic algorithm for very large numbers (used in cryptography). It’s fast and reliable but has a tiny error probability.
• AKS Primality Test: A deterministic polynomial-time algorithm—but too complex for manual use.

Pro Tips & Common Mistakes

• 1 is not prime: This is a common misconception. Primes must have exactly two divisors.
• Check √n, not n: Testing up to n is unnecessary and inefficient.
• Use factor trees for clarity: They prevent missed factors in complex numbers.
• Memorise small primes: Knowing primes up to 100 speeds up manual testing.
• For even numbers > 2: They’re always composite—no need to test further.

Practical Applications

• Cryptography: RSA encryption relies on the difficulty of factoring large semiprimes.
• Mathematics: Simplifying fractions, finding GCF/LCM, solving Diophantine equations.
• Computer Science: Hash functions, random number generation, algorithm design.
• Education: Building number sense and logical reasoning in students.