Prime Check: Square Root Trial Division Pattern

Learning Outcome

After this lesson, you should be able to prove why a composite number must have a factor at or below square root of n.

Problem Statement

Given an integer n, return true if n is prime and false otherwise.

Brute Force Approach

Try every divisor from 2 to n

• 1. This is easy to understand but wastes many checks.

Optimized Approach

Handle small numbers first, reject multiples of 2 and 3, then test candidates of the form 6k

• 1 and 6k + 1 while i * i is at most n.

Exact Pseudocode

if n < 2:
  return false
if n is 2 or 3:
  return true
if n is divisible by 2 or 3:
  return false
i = 5
while i * i <= n:
  if n is divisible by i or i + 2:
    return false
  i += 6
return true
  

Reference Code

class Solution:
    def isPrime(self, n):
        if n < 2:
            return False
        if n == 2 or n == 3:
            return True
        if n % 2 == 0 or n % 3 == 0:
            return False

        i = 5
        while i * i <= n:
            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
        return True
  

Sample Dry Run

Complexity

Edge Cases

• n less than 2 is not prime.
• 2 and 3 are prime.
• Perfect squares like 49 must be caught, so use i * i at most n.

Interview Checklist

• Handle small values before the loop.
• Reject even numbers and multiples of 3 early.

• Test 6k

  • 1 and 6k + 1 candidates only.

FAQs

If both factors were larger than square root of n, their product would be larger than n.

Every prime greater than 3 is beside a multiple of 6, so other candidates can be skipped.

Square-root trial division.