Find the count of numbers which are not special

Array Math Number Theory

27.5% acceptance

Feb 25, 2026

196

You are given two positive integers l and r. A positive integer is called special if only 1 and the number itself are the positive divisors of the number. Wait, this problem actually says: "The integers are special if they have exactly 2 divisors". Actually re-reading: the problem title says "numbers which are not special". A number is "special" if it has exactly 2 divisors (i.e., it is prime? No, the problem actually means numbers that have exactly 2 factors: 1 and itself... but let me re-read. A positive integer is called special if it has exactly 2 factors. Wait -- actually the problem might define special differently. Let me re-state from problem: "Find the Count of Numbers Which Are Not Special" A positive integer num is considered special if the only divisors of num are 1 and num itself. Hmm that would be primes. But wait, this problem is about squares of primes: return the count of integers in [l, r] that are NOT special. Special = has exactly 3 divisors = p^2 for some prime p. (since p^2 has divisors 1, p, p^2) Given 1 <= l <= r <= 10^9. Example 1 (from typical LeetCode 3233): Input: l = 5, r = 7 -> Output: 3 (none are special in [5,7]) Actually: let's use sieve to count primes up to sqrt(r). A special number x in [l, r] with exactly 3 divisors means x = p^2 for prime p, and p <= sqrt(r). Count = r - l + 1 - count_of_special_in_range.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn non_special_count(l: i32, r: i32) -> i32 {
    let limit = (r as f64).sqrt() as i32 + 1;
    // Sieve of Eratosthenes up to limit
    let mut is_prime = vec![true; (limit + 1) as usize];
    is_prime[0] = false;
    if limit >= 1 { is_prime[1] = false; }
    let mut p = 2;
    while p * p <= limit {
      if is_prime[p as usize] {
        let mut multiple = p * p;
        while multiple <= limit {
          is_prime[multiple as usize] = false;
          multiple += p;
        }
      }
      p += 1;
    }
    // Count special numbers: p^2 in [l, r]
    let mut special = 0i32;
    for p in 2..=limit {
      if is_prime[p as usize] {
        let sq = p as i64 * p as i64;
        if sq >= l as i64 && sq <= r as i64 {
          special += 1;
        }
      }
    }
    (r - l + 1) - special
  }
}