Primes & Factors
Is this number prime? What are its factors? The naive checks are slow, and the fast ones are surprisingly clever.
The problem
A form on your site asks users to pick a "lucky number," and you want to award a badge if it happens to be prime. Simple enough — you write a checker. Then a prankster pastes in 999999937 and your request times out. The badge feature has become a denial-of-service hole.
The naive way to test primality is the first thing everyone writes, and it is also the thing that falls over on big inputs. The fast way needs only one insight about how factors come in pairs.
A first attempt
Test every possible divisor from 2 up to n - 1:
def is_prime_slow(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return TrueCorrect, but it does up to n - 2 divisions. That is O(n) — for a 9-digit number like 999999937 that is nearly a billion modulo operations, which is exactly why your request hung. To make this practical you need to check far fewer candidates.
The insight
Factors come in pairs. If d divides n, then so does n / d, and the two multiply back to n. In every such pair, one member is ≤ √n and the other is ≥ √n. So if n had any divisor at all, the smaller one would already appear at or below √n.
That means you never have to look past √n. Find no divisor there, and there is none anywhere.
- For
n = 100, √n = 10. The pairs are(2,50), (4,25), (5,20), (10,10)— every small side is≤ 10. - Checking up to
√ninstead ofndrops a billion operations to about 31,623 for that 9-digit number.
The same pairing insight lets you list all factors in O(√n): for each d ≤ √n that divides n, record both d and n / d.
How it works
Rule out the trivial cases
Numbers below 2 are not prime by definition, so return early. This also keeps the loop below from misbehaving on 0 and 1.
Loop only while i·i ≤ n
Instead of computing a floating-point √n, test i * i <= n. This stays in integer arithmetic — no rounding bugs — and stops exactly at the square root.
Reject on the first divisor
If any i divides n evenly, n is composite; return false immediately. You do not need the other factor, just the fact that one exists.
is_prime(97): test i = 2,3,4,5,6,7,8,9
9*9 = 81 ≤ 97, 10*10 = 100 > 97 -> stop
none divide 97 -> primeCollect both sides for factors
To list factors, whenever i divides n, record i and its partner n / i. Guard the case i == n / i (a perfect square) so you don't add the square root twice.
The code
def is_prime(n): # O(sqrt n)
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
def factors(n): # O(sqrt n)
result = []
i = 1
while i * i <= n:
if n % i == 0:
result.append(i)
if i != n // i:
result.append(n // i)
i += 1
return sorted(result)
print(is_prime(97)) # True
print(factors(36)) # [1, 2, 3, 4, 6, 9, 12, 18, 36]function isPrime(n: number): boolean {
if (n < 2) return false;
for (let i = 2; i * i <= n; i++) {
if (n % i === 0) return false;
}
return true;
}
function factors(n: number): number[] {
const result: number[] = [];
for (let i = 1; i * i <= n; i++) {
if (n % i === 0) {
result.push(i);
if (i !== n / i) result.push(n / i);
}
}
return result.sort((a, b) => a - b);
}
console.log(isPrime(97)); // true
console.log(factors(36)); // [1, 2, 3, 4, 6, 9, 12, 18, 36]static boolean isPrime(int n) { // O(sqrt n)
if (n < 2) return false;
for (int i = 2; (long) i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
static java.util.List<Integer> factors(int n) {
java.util.List<Integer> result = new java.util.ArrayList<>();
for (int i = 1; (long) i * i <= n; i++) {
if (n % i == 0) {
result.add(i);
if (i != n / i) result.add(n / i);
}
}
java.util.Collections.sort(result);
return result;
}
// isPrime(97) -> true, factors(36) -> [1, 2, 3, 4, 6, 9, 12, 18, 36]#include <stdbool.h>
bool is_prime(int n) { /* O(sqrt n) */
if (n < 2) return false;
for (int i = 2; (long)i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
/* factors: fill out[] with divisors, return the count */
int factors(int n, int out[]) { /* O(sqrt n) */
int count = 0;
for (int i = 1; (long)i * i <= n; i++) {
if (n % i == 0) {
out[count++] = i;
if (i != n / i) out[count++] = n / i;
}
}
return count; /* caller may sort out[] */
}
/* is_prime(97) -> true */#include <vector>
#include <algorithm>
bool isPrime(int n) { // O(sqrt n)
if (n < 2) return false;
for (int i = 2; (long long)i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
std::vector<int> factors(int n) { // O(sqrt n)
std::vector<int> result;
for (int i = 1; (long long)i * i <= n; i++) {
if (n % i == 0) {
result.push_back(i);
if (i != n / i) result.push_back(n / i);
}
}
std::sort(result.begin(), result.end());
return result;
}
// isPrime(97) -> true, factors(36) -> [1, 2, 3, 4, 6, 9, 12, 18, 36]Complexity
| Task | Approach | Time | Space |
|---|---|---|---|
| Primality (naive) | trial up to n | O(n) | O(1) |
| Primality (√n trial) | trial up to √n | O(√n) | O(1) |
| List all factors | pair up around √n | O(√n) | O(√n) |
| Primes up to N | Sieve of Eratosthenes | O(N log log N) | O(N) |
For testing one number, √n trial division wins. For finding all primes up to some limit, the sieve is the right tool — that is a separate lesson.
When to use it
√n trial division has limits
Trial division to √n is perfect for a single check on numbers up to roughly 10¹²ish. Beyond that — cryptographic-scale numbers with hundreds of digits — even √n is astronomically large, and you need probabilistic tests like Miller–Rabin. And if you must test many numbers below a fixed bound, precompute a sieve once instead of running trial division over and over.
Practice
Recap
- Factors come in pairs straddling
√n, so you never need to search past the square root. - Trial division to
√ntests primality in O(√n); the same loop lists all factors in O(√n). - Use
i * i <= nfor exact integer bounds, and switch to a sieve when you need many primes at once.
How is this guide?
Last updated on