Frontend School

K-Prime Number Counter

DSA
medium

K-Prime Number Counter

Medium
Math
Number Theory
Sieve
Prime Factorization

Overview

In data analysis and cryptography, numbers with a specific count of distinct prime factors can exhibit interesting properties. For instance, highly composite numbers often have many distinct prime factors, while prime numbers themselves have exactly one. Understanding and efficiently identifying such numbers within a given range is a fundamental problem with applications in hashing, random number generation, and certain cryptographic schemes.

This problem asks you to count numbers within a specified range [L, R] that have exactly K distinct prime factors. We'll refer to such numbers as "K-prime" numbers.

What you need to do / Task

Implement the function countKPrimeNumbers which takes three integer arguments: L, R, and K. Your task is to return the total count of numbers N such that L <= N <= R and N has exactly K distinct prime factors.

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).
    • K: An integer representing the exact number of distinct prime factors a number must have.
  • Output:

    • An integer representing the total count of K-prime numbers within the range [L, R].

Clarifications

  • A number N is considered K-prime if, when N is expressed as a product of its prime factors (e.g., N = p1^a1 * p2^a2 * ... * pk^ak), there are exactly K distinct prime numbers p1, p2, ..., pk.
  • For example:
    • 6 = 2 * 3 has 2 distinct prime factors (2 and 3), so it is 2-prime.
    • 12 = 2^2 * 3 also has 2 distinct prime factors (2 and 3), so it is 2-prime.
    • 30 = 2 * 3 * 5 has 3 distinct prime factors (2, 3, and 5), so it is 3-prime.
    • 7 = 7 has 1 distinct prime factor (7), so it is 1-prime (i.e., a prime number).
    • 1 is conventionally considered to have 0 distinct prime factors, and thus is not K-prime for any K >= 1.

Examples

1

Example 1

Input:

L = 1, R = 10, K = 1

Output:

4

Note:

The 1-prime numbers (primes) in the range [1, 10] are: 2, 3, 5, 7. There are 4 such numbers.

2

Example 2

Input:

L = 1, R = 30, K = 2

Output:

12

Note:

The 2-prime numbers in the range [1, 30] are: 6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28. There are 12 such numbers. (Note: 30 = 235 is 3-prime, not 2-prime).

3

Example 3

Input:

L = 60, R = 70, K = 3

Output:

3

Note:

The 3-prime numbers in the range [60, 70] are: 60 (235), 66 (2311), 70 (257). There are 3 such numbers.

Constraints

Constraints & assumptions

  • 1 <= L <= R <= 5 * 10^6
  • 1 <= K <= 7
  • The solution should be efficient enough to pass within typical time limits (e.g., 2-3 seconds) and memory limits (e.g., 256 MB).

Out of scope

  • Handling R values significantly larger than 10^7 that would require advanced techniques like segmented sieves or Pollard's Rho algorithm.
  • Optimizations specifically for K=1 (counting primes) that deviate from the general K-prime counting logic.

What interviewers evaluate

  • Correctness and Efficiency: Your ability to accurately count K-prime numbers using an algorithm that scales well within the given constraints.
  • Algorithm Design: Demonstrating a strong understanding of number theory concepts, particularly efficient prime factorization or sieve methods.
  • Code Quality: Clarity, structure, and maintainability of your code, including appropriate data structures and variable naming.
  • Edge Case Handling: Correctly addressing edge cases such as L=1, K=1, or ranges where no K-prime numbers exist.

Loading editor...