Primality Testing up to sqrt(n)
Check a single number efficiently.
Primality Testing up to sqrt(n) is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Prime Question
A core math skill is deciding if a single number is prime. A prime has exactly two divisors: one and itself. Let us test it fast. 🔍
The Naive Check
You could try dividing n by every number from 2 up to n minus 1. It is correct but painfully slow when n is large.
The Square Root Trick
Here is the key insight: you only need to test divisors up to the square root of n. Beyond that, no new factor can appear.
Why Sqrt Is Enough
Divisors come in pairs that multiply to n. If both were above the square root, their product would exceed n, which is impossible.
The Loop Bound
Iterate i from 2 while i times i stays at or below n. Using i*i avoids floating-point error from sqrt on big integers.
while i * i <= n:
...Handle Small Cases
Numbers below 2 are never prime, so reject them up front. This guard keeps your main loop clean and correct.
if n < 2:
return FalseThe Full Function
Put it together: guard small values, then scan possible divisors up to the root. Any clean division means n is composite.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return TrueSpeed It Up
Check 2 separately, then test only odd numbers. Skipping evens roughly halves the work for no extra complexity.
if n % 2 == 0:
return n == 2The Time Cost
This test runs in O(sqrt n) time. For a single number up to a billion that is only about 30,000 cheap operations.
One Number, Not Many
The sqrt test shines for one or a few queries. If you need primality for a whole range, a sieve will be far faster.
Avoid the Sqrt Pitfall
Comparing with i*i instead of math.sqrt sidesteps rounding errors that can wrongly accept or reject borderline numbers.
Quick Check
Confirm the bound that makes this test fast.
Recap
You can now test one number for primality in O(sqrt n) time, guard small values, skip evens, and use i*i to stay exact. ✅
Frequently asked questions
Is the “Primality Testing up to sqrt(n)” lesson free?
Yes — the full text of “Primality Testing up to sqrt(n)” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Primality Testing up to sqrt(n)”?
Check a single number efficiently. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Primality Testing up to sqrt(n)” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- GCD, LCM & the Euclidean Algorithm
- Primality Testing up to sqrt(n)
- Sieve of Eratosthenes
- Prime Factorization & Divisors