# 3233. Find the Count of Numbers Which Are Not Special

## Description

You are given 2 positive integers l and r. For any number x, all positive divisors of x except x are called the proper divisors of x.

A number is called special if it has exactly 2 proper divisors. For example:

• The number 4 is special because it has proper divisors 1 and 2.
• The number 6 is not special because it has proper divisors 1, 2, and 3.

Return the count of numbers in the range [l, r] that are not special.

Example 1:

Input: l = 5, r = 7

Output: 3

Explanation:

There are no special numbers in the range [5, 7].

Example 2:

Input: l = 4, r = 16

Output: 11

Explanation:

The special numbers in the range [4, 16] are 4 and 9.

Constraints:

• 1 <= l <= r <= 109

## Solutions

### Solution 1: Mathematics

According to the problem description, we can observe that only the squares of prime numbers are special numbers. Therefore, we can first preprocess all prime numbers less than or equal to $\sqrt{10^9}$, and then iterate through the interval $[\lceil\sqrt{l}\rceil, \lfloor\sqrt{r}\rfloor]$, counting the number of primes $\textit{cnt}$ in the interval. Finally, we return $r - l + 1 - \textit{cnt}$.

The time complexity is $O(\sqrt{m})$, and the space complexity is $O(\sqrt{m})$, where $m = 10^9$.

• class Solution {
static int m = 31623;
static boolean[] primes = new boolean[m + 1];

static {
Arrays.fill(primes, true);
primes[0] = primes[1] = false;
for (int i = 2; i <= m; i++) {
if (primes[i]) {
for (int j = i + i; j <= m; j += i) {
primes[j] = false;
}
}
}
}

public int nonSpecialCount(int l, int r) {
int lo = (int) Math.ceil(Math.sqrt(l));
int hi = (int) Math.floor(Math.sqrt(r));
int cnt = 0;
for (int i = lo; i <= hi; i++) {
if (primes[i]) {
cnt++;
}
}
return r - l + 1 - cnt;
}
}

• const int m = 31623;
bool primes[m + 1];

auto init = [] {
memset(primes, true, sizeof(primes));
primes[0] = primes[1] = false;
for (int i = 2; i <= m; ++i) {
if (primes[i]) {
for (int j = i * 2; j <= m; j += i) {
primes[j] = false;
}
}
}
return 0;
}();

class Solution {
public:
int nonSpecialCount(int l, int r) {
int lo = ceil(sqrt(l));
int hi = floor(sqrt(r));
int cnt = 0;
for (int i = lo; i <= hi; ++i) {
if (primes[i]) {
++cnt;
}
}
return r - l + 1 - cnt;
}
};

• m = 31623
primes = [True] * (m + 1)
primes[0] = primes[1] = False
for i in range(2, m + 1):
if primes[i]:
for j in range(i + i, m + 1, i):
primes[j] = False

class Solution:
def nonSpecialCount(self, l: int, r: int) -> int:
lo = ceil(sqrt(l))
hi = floor(sqrt(r))
cnt = sum(primes[i] for i in range(lo, hi + 1))
return r - l + 1 - cnt


• const m = 31623

var primes [m + 1]bool

func init() {
for i := range primes {
primes[i] = true
}
primes[0] = false
primes[1] = false
for i := 2; i <= m; i++ {
if primes[i] {
for j := i * 2; j <= m; j += i {
primes[j] = false
}
}
}
}

func nonSpecialCount(l int, r int) int {
lo := int(math.Ceil(math.Sqrt(float64(l))))
hi := int(math.Floor(math.Sqrt(float64(r))))
cnt := 0
for i := lo; i <= hi; i++ {
if primes[i] {
cnt++
}
}
return r - l + 1 - cnt
}

• const m = 31623;
const primes: boolean[] = Array(m + 1).fill(true);

(() => {
primes[0] = primes[1] = false;
for (let i = 2; i <= m; ++i) {
if (primes[i]) {
for (let j = i * 2; j <= m; j += i) {
primes[j] = false;
}
}
}
})();

function nonSpecialCount(l: number, r: number): number {
const lo = Math.ceil(Math.sqrt(l));
const hi = Math.floor(Math.sqrt(r));
let cnt = 0;
for (let i = lo; i <= hi; ++i) {
if (primes[i]) {
++cnt;
}
}
return r - l + 1 - cnt;
}