Easy · Trial Division to Square Root
Understand → Visualise → Practice.
Return whether n is prime using no precomputed table.
If n has a factor, it has one no larger than √n. Check 2 separately, then only odd divisors up to √n.
Numbers below 2 are not prime; 2 is prime; other even numbers are not.
Test d = 3, 5, 7, … while d × d ≤ n.
Any exact division means composite; otherwise n is prime.
O(√n) time and O(1) space.
Testing divisors all the way to n − 1 is O(n).
Read the full guide first: Number Theory Basics for Algorithms.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.