Chapter 18
HomeA prime is a number greater than 1 that has no divisors other than 1 and itself. The simplest way to check primality is trial division.
Try dividing by every integer from 2 up to N−1. If none divide evenly, N is prime.
bool is_prime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
Only check up to √N — if a divisor exists, one must be ≤ √N.
fn is_prime(n: u32) -> bool {
if n < 2 { return false; }
let limit = (n as f64).sqrt() as u32;
for i in 2..=limit {
if n % i == 0 { return false; }
}
true
}
💡 Why √N?
If N = a × b, at least one of a or b must be ≤ √N. So checking up to √N is sufficient — it reduces the complexity from O(N) to O(√N).
for (int i = 2; i <= n; i++) {
if (is_prime(i)) cout << i << " ";
}
let primes: Vec<u32> = (2..=n).filter(|&i| is_prime(i)).collect();
📐 Complexity
Naive trial division for a single number is O(√N). For all numbers up to N, it's O(N√N) — too slow for N=10⁶. The next chapter fixes this.