Primality Testing up to sqrt(n)
Check a single number efficiently.
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.
All lessons in this course
- GCD, LCM & the Euclidean Algorithm
- Primality Testing up to sqrt(n)
- Sieve of Eratosthenes
- Prime Factorization & Divisors