Frontend School

Count K-Prime Distinct Numbers in a Range

DSA
medium

Count K-Prime Distinct Numbers in a Range

Medium
Math
Number Theory
Sieve
Prefix Sum

Overview

In various computational number theory applications, efficiently categorizing numbers based on their prime factor profiles is crucial. This problem asks you to identify and count numbers within a given range [L, R] that possess a specific count of distinct prime factors. Such functionality can be used in optimizing database queries, cryptographic algorithms, or specialized scientific simulations requiring number-theoretic properties.

What you need to do / Task

Implement the function countKPrimeDistinct(L, R, K) that returns the total count of integers x such such that L <= x <= R and x has exactly K distinct prime factors.

Input & output

  • L: An integer representing the lower bound of the range (inclusive).
  • R: An integer representing the upper bound of the range (inclusive).
  • K: An integer representing the exact number of distinct prime factors required.
  • The function should return a single integer: the count of numbers in [L, R] with exactly K distinct prime factors.

Clarifications

  • Numbers are considered to have distinct prime factors. For example, 12 = 2^2 * 3 has two distinct prime factors (2 and 3), not three. 8 = 2^3 has one distinct prime factor (2).
  • The number 1 has zero distinct prime factors and should not be counted unless K=0 is explicitly allowed (which it isn't in the constraints for this problem, K >= 1).
  • Prime numbers themselves have exactly one distinct prime factor (e.g., 7 has 7 as its only distinct prime factor).

Examples

1

Example 1

Input:

L = 1, R = 10, K = 1

Output:

7

Note:

Numbers in [1, 10] with exactly 1 distinct prime factor are: 2 (prime), 3 (prime), 4 (2^2), 5 (prime), 7 (prime), 8 (2^3), 9 (3^2). Count = 7.

2

Example 2

Input:

L = 10, R = 20, K = 2

Output:

6

Note:

Numbers in [10, 20] with exactly 2 distinct prime factors are: 10 (25), 12 (2^23), 14 (27), 15 (35), 18 (23^2), 20 (2^25). Count = 6.

3

Example 3

Input:

L = 1, R = 30, K = 3

Output:

1

Note:

The smallest number with exactly 3 distinct prime factors is 235 = 30. In the range [1, 30], only 30 satisfies this condition. Count = 1.

Constraints

Constraints & assumptions

  • 1 <= L <= R <= 10^6
  • 1 <= K <= 7
  • L, R, and K are integers.

Out of scope

  • Handling extremely large ranges (e.g., R > 10^7) that would necessitate more advanced number-theoretic sieving techniques (like segmented Sieve, Meissel-Lehmer algorithm, or related methods) which are beyond the typical scope for a 40-minute L5 coding round.

What interviewers evaluate

  • Correctness: The solution must accurately count all numbers satisfying the criteria within the given range and constraints.
  • Efficiency: The algorithm should be optimized for the given R constraint, demonstrating an understanding of precomputation techniques.
  • Edge Cases: Proper handling of boundaries, small K values, and ranges starting from 1.
  • Clarity: The code should be well-structured, readable, and easy to understand.

Loading editor...