Frontend School

Count Bi-Prime Numbers in Range

DSA
medium

Count Bi-Prime Numbers in Range

Medium
Math
Number Theory
Sieve
Prime Numbers

Overview

In various cryptographic and number theory applications, numbers with specific prime factorizations play a crucial role. For instance, numbers that are products of exactly two distinct primes are often used in generating public keys or for specific hashing algorithms due to their unique properties and the computational difficulty of factoring large numbers. This problem challenges you to identify and count such "bi-prime" numbers within a given integer range.

What you need to do / Task

Your task is to implement a function that takes two integers, L and R, representing a closed range [L, R], and returns the total count of bi-prime numbers within this range. A bi-prime number is defined as a positive integer that is the product of exactly two distinct prime numbers.

Input & output

  • Input:
    • L: An integer representing the lower bound of the range (inclusive).
    • R: An integer representing the upper bound of the range (inclusive).
  • Output:
    • An integer representing the count of bi-prime numbers in the range [L, R].

Clarifications

  • The range [L, R] is inclusive, meaning both L and R can be bi-prime numbers and should be counted if they are.
  • Prime numbers are positive integers greater than 1 that have no positive divisors other than 1 and themselves. Examples: 2, 3, 5, 7, 11, ...
  • "Distinct prime numbers" means the two primes multiplied together must be different. For example, 6 (2 * 3) is bi-prime, but 4 (2 * 2) is not.
  • The problem asks for positive integers.

Examples

1

Example 1

Input:

L = 1, R = 20

Output:

4

Note:

The bi-prime numbers in [1, 20] are: 6 (23), 10 (25), 14 (27), and 15 (35).

2

Example 2

Input:

L = 20, R = 30

Output:

3

Note:

The bi-prime numbers in [20, 30] are: 21 (37), 22 (211), and 26 (2*13).

3

Example 3

Input:

L = 4, R = 5

Output:

0

Note:

Neither 4 (2*2) nor 5 (a prime number) is a bi-prime number.

Constraints

Constraints & assumptions

  • 1 <= L <= R <= 10^9
  • The input L and R will always be valid integers within the specified range.

What interviewers evaluate

  • Algorithmic Efficiency: Ability to devise an algorithm that efficiently handles large input ranges, particularly for R up to 10^9.
  • Correctness: The solution must accurately identify and count all bi-prime numbers within the specified range, adhering to the definition.
  • Edge Cases: Proper handling of small ranges, ranges containing no bi-prime numbers, or ranges where L and R are bi-primes.
  • Code Quality: Clean, readable, and well-structured code with appropriate variable names.

Loading editor...