3233. Find the Count of Numbers Which Are Not Special

Posted on Edited on In

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:

1
2
3
Input: l = 5, r = 7

Output: 3

Explanation:

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

Example 2:

1
2
3
Input: l = 4, r = 16

Output: 11

Explanation:

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

Constraints:

  • 1 <= l <= r <= 10^9

Hints/Notes

  • 2024/08/01
  • only value that’s square of prime number satisfies the need
  • 0x3F’s solution(checked)
  • Weekly Contest 408

Solution

Language: C++

Pre-calculate the prime numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int MX = 31622;
int pi[MX + 1];

auto init = [] {
    for (int i = 2; i <= MX; i++) {
        if (pi[i] == 0) {
            pi[i] = pi[i - 1] + 1;
            for (int j = i * i; j <= MX; j += i) {
                pi[j] = -1;
            }
        } else {
            pi[i] = pi[i - 1];
        }
    }
    return 0;
}();

// to calculate the number of prime numbers within l and r
res = pi[r] - pi[l - 1]
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
class Solution {
public:
    int nonSpecialCount(int l, int r) {
        int count = 0;
        for (int i = 0; i * i <= r; i++) {
            if (i * i < l) {
                continue;
            }
            if (isPrime(i)) {
                count++;
            }
        }
        return r - l + 1 - count;
    }

    bool isPrime(int n) {
        if (n == 1) {
            return false;
        }
        int i = 2;
        while (i * i <= n) {
            if (n % i == 0) {
                return false;
            }
            i++;
        }
        return true;
    }
};