Frontend School

Count Shiprocket-Prime Numbers

DSA
medium

Count Shiprocket-Prime Numbers

Medium
Math
Number Theory
Sieve
Prime Factorization

Overview

At Shiprocket, optimizing our logistics and data processing often involves identifying special patterns in numerical data, which can range from parcel IDs to internal system metrics. To enhance our analytical capabilities, we've defined a new category of numbers: a "Shiprocket-Prime Number." These numbers hold unique properties that could be leveraged for data segmentation or cryptographic hashing. Your task is to identify and count these special numbers within a given range.

A number K is defined as a "Shiprocket-Prime Number" if the sum of its distinct prime factors is itself a prime number.

For example:

  • K = 10. Its distinct prime factors are 2 and 5. The sum is 2 + 5 = 7. Since 7 is a prime number, 10 is a Shiprocket-Prime Number.
  • K = 12. Its distinct prime factors are 2 and 3. The sum is 2 + 3 = 5. Since 5 is a prime number, 12 is a Shiprocket-Prime Number.
  • K = 30. Its distinct prime factors are 2, 3, and 5. The sum is 2 + 3 + 5 = 10. Since 10 is not a prime number, 30 is NOT a Shiprocket-Prime Number.

What you need to do / Task

Your task is to implement a function countShiprocketPrimes that takes an integer N and returns the total count of Shiprocket-Prime Numbers between 2 and N (inclusive).

Input & output

  • Input: An integer N.
    • N: The upper bound (inclusive) for checking Shiprocket-Prime Numbers.
  • Output: An integer representing the count of Shiprocket-Prime Numbers from 2 to N.

Clarifications

  • Numbers less than 2 (i.e., 0, 1) do not have prime factors in the context of this problem and should not be considered Shiprocket-Prime. Your count should start from 2.
  • A prime number P has only one distinct prime factor, which is P itself. The sum of its distinct prime factors is P. If P is prime, then P is a Shiprocket-Prime number.

Examples

1

Example 1

Input:

N = 1

Output:

0

Note:

No numbers from 2 to 1 (inclusive) exist. So the count is 0.

2

Example 2

Input:

N = 10

Output:

9

Note:

Numbers 2, 3, 4, 5, 6, 7, 8, 9, 10 are Shiprocket-Prime:

  • 2: {2}, sum=2 (prime)
  • 3: {3}, sum=3 (prime)
  • 4: {2}, sum=2 (prime)
  • 5: {5}, sum=5 (prime)
  • 6: {2,3}, sum=5 (prime)
  • 7: {7}, sum=7 (prime)
  • 8: {2}, sum=2 (prime)
  • 9: {3}, sum=3 (prime)
  • 10: {2,5}, sum=7 (prime) Total count = 9.
3

Example 3

Input:

N = 20

Output:

17

Note:

Building on N=10 (9 Shiprocket-Primes):

  • 11: {11}, sum=11 (prime)
  • 12: {2,3}, sum=5 (prime)
  • 13: {13}, sum=13 (prime)
  • 14: {2,7}, sum=9 (not prime)
  • 15: {3,5}, sum=8 (not prime)
  • 16: {2}, sum=2 (prime)
  • 17: {17}, sum=17 (prime)
  • 18: {2,3}, sum=5 (prime)
  • 19: {19}, sum=19 (prime)
  • 20: {2,5}, sum=7 (prime) Numbers 11, 12, 13, 16, 17, 18, 19, 20 are Shiprocket-Prime (8 numbers). Total count = 9 + 8 = 17.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^6
  • The input N will always be a positive integer.
  • Time Limit: ~1-2 seconds
  • Memory Limit: ~256 MB

What interviewers evaluate

  • Correctness: The solution must correctly identify and count Shiprocket-Prime Numbers for all valid inputs, including edge cases.
  • Efficiency: The solution should be optimized for the given constraints, demonstrating an understanding of efficient number theory algorithms (e.g., sieve methods).
  • Code Quality: The code should be clean, readable, well-structured, and follow reasonable coding practices.
  • Problem-Solving Approach: The candidate's ability to break down the problem, choose appropriate data structures and algorithms, and handle intermediate calculations effectively.

Loading editor...