Count primes

Array Math Enumeration Number Theory

35.8% acceptance

Jan 12, 2026

8765

1576

Given an integer n, return the number of prime numbers that are strictly less than n.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_primes(n: i32) -> i32 {
    if n <= 2 { return 0; }
    let n = n as usize;
    let mut is_prime = vec![true; n];
    is_prime[0] = false;
    is_prime[1] = false;
    
    let mut i = 2;
    while i * i < n {
      if is_prime[i] {
        let mut j = i * i;
        while j < n {
          is_prime[j] = false;
          j += i;
        }
      }
      i += 1;
    }
    is_prime.iter().filter(|&&x| x).count() as i32
  }
}