Faangprep Logo
Log inStart free
Browse curriculum

Prime Numbers

Determine if a number is prime using Trial Division.

TEST TO √29 ≈ 5 · DIMMED = BEYOND THE BOUND

BOUND

29

2
3
4
5
6
7
8
9
10
11
12
13
14

Testing

—

Tests used

0

 

Test divisors from 2 up to √29 ≈ 5. Anything larger cannot be the smaller half of a factor pair, so it cannot be the first divisor found.

Next

29 mod 2 = 1, so 2 is not a divisor.

N

29

Intuition

To check if a number N is prime, we try to divide it by every number from 2 up to N-1. If none divide it evenly, it's prime.

Concept

  • Prime Number: A number greater than 1 that has exactly two factors: 1 and itself.
  • Composite Number: A number that has more than two factors.
  • Optimization: We only need to check divisors up to √N. If N has a factor larger than √N, it must also have a corresponding factor smaller than √N.

How it Works

Algorithm:

  1. If N ≤ 1, return False.
  2. Loop i from 2 to √N.
  3. If N % i == 0, return False (found a factor).
  4. If loop finishes without finding a factor, return True.

Step-by-Step Breakdown

Watch the visualization:

  • The solid blue cell is the divisor being tested.
  • Grey, struck-through cells are divisors already tested that do not divide N; the faint ones past √N are never tested.
  • A red cell is a divisor that divides N, which proves N is composite.
  • N itself turns green if it is prime and red if it is not.
  • Notice we stop early if we find a factor!

Trace: isPrime(91), then isPrime(29)

91: bound

√91 is about 9.54, so the loop only has to reach 9. A factor above 9 would have a partner below 9, and the scan would have met the partner first.

test 3, 5, 7, 9

91 % 3

Not zero. 91 is odd, so 2 never needed testing and the loop steps by two.

continue

91 % 5

Not zero.

continue

91 % 7

Zero. 91 is 7 * 13, so the answer is settled here and 9 is never reached.

composite

29: bound

√29 is about 5.39, so the loop reaches 5.

test 3, 5

29 % 3, % 5

Neither is zero, and the loop ends having found nothing. For a prime there is no early exit to take — the full bound is the price of the answer.

prime

note

Three divisions to reject 91 and two to accept 29. Testing every divisor up to 90 instead of up to 9 would have given the same two answers for roughly ten times the work, and the ratio grows as √N against N.

5 divisions

When to Use

  • Checking primality for small to medium numbers (up to 10^12 is feasible).
  • Cryptography key generation (though probabilistic tests like Miller-Rabin are used for huge numbers).

When NOT to Use

  • For extremely large numbers (hundreds of digits).
  • When you need to generate many primes (use Sieve of Eratosthenes instead).

How to Identify

"Is N prime?", "Find factors", "Number theory problems".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

GCD / LCM

Next

Sieve of Eratosthenes

Frequently Asked Questions

Why is it enough to test divisors up to √N?

Factors come in pairs that multiply to N. If N had a factor above √N its partner would be below √N, and trial division would have found that one first. So no factor above √N can ever be the first one found.

Do I need to test even divisors?

Only 2. Once 2 is ruled out every remaining factor is odd, so you can start at 3 and step by 2, which halves the work.

When is trial division the wrong tool?

When you need every prime below a limit, where the Sieve of Eratosthenes is far faster, and when N has hundreds of digits, where probabilistic tests such as Miller-Rabin are used instead.