Skip to content

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

Thinking

A special number has exactly three positive divisors, i.e. it is the square of a prime. \(l,r\le 10^9\), so trial-dividing every integer in the range is impossible.

Special numbers in \([l,r]\) correspond to primes in \([\lceil\sqrt{l}\rceil,\lfloor\sqrt{r}\rfloor]\). After a sieve up to \(\sqrt{10^9}\), count those primes and subtract from the interval length.

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\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
}

Comments