Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3507. Find the Count of Numbers Which Are Not Special

My accepted Python solution to LeetCode problem 3507, Find the Count of Numbers Which Are Not Special, running in 227ms.

  • Difficulty: Medium
  • Python
  • Runtime 227ms
  • Memory 17.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 227ms, memory 17.5MB, accepted 2025-12-30.

python
class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:
        import math
        max_p = int(math.sqrt(r)) + 1
        sieve = [True] * (max_p + 1)
        sieve[0] = sieve[1] = False
        for i in range(2, int(math.sqrt(max_p)) + 1):
            if sieve[i]:
                for j in range(i*i, max_p + 1, i):
                    sieve[j] = False
        cnt = 0
        for p in range(2, max_p + 1):
            if sieve[p] and l <= p*p <= r:
                cnt += 1
        return r - l + 1 - cnt

Source