Back

3507. Find the Count of Numbers Which Are Not Special

Medium
Array
Math
Number Theory
Solve on LeetCode View Solutions

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

Hints

Hint 1
A special number must be a square of a prime number.
Hint 2
We need to find all primes in the range <code>[sqrt(l), sqrt(r)]</code>.
Hint 3
Use sieve to find primes till <code>sqrt(10<sup>9</sup>)</code>.

Similar Questions

Count Primes
Medium

Statistics

Acceptance
27.4%
Submissions
135,025
Accepted
37,050