Frontend School

Check if a Number is Semi-Prime

DSA
easy

Check if a Number is Semi-Prime

Easy
Math
Number Theory
Prime Numbers
Factorization

Overview

In various cryptographic algorithms and number theory applications, numbers with specific prime factor properties play a crucial role. One such category is semi-prime numbers, which are integers that are the product of exactly two prime numbers (they can be the same). Understanding and identifying these numbers is fundamental for tasks like key generation and factorization challenges.

What you need to do / Task

Implement a function that determines if a given positive integer n is a semi-prime number.

  1. A semi-prime number is defined as a natural number that is the product of exactly two prime numbers. These prime numbers do not have to be distinct.
  2. For example, 4 (2 * 2), 6 (2 * 3), 9 (3 * 3), 10 (2 * 5), and 14 (2 * 7) are semi-prime numbers.
  3. Numbers like 1, 2, 3, 5, 7 (primes), 8 (2 * 2 * 2), 12 (2 * 2 * 3) are NOT semi-prime.

Input & output

  • n: An integer representing the number to check.
  • Return true if n is a semi-prime number, false otherwise.

Clarifications

  • The input n will always be a positive integer.
  • A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Examples

1

Example 1

Input:

n = 6

Output:

true

Note:

6 is 2 * 3. Both 2 and 3 are prime numbers.

2

Example 2

Input:

n = 4

Output:

true

Note:

4 is 2 * 2. 2 is a prime number, and 4 is a product of two primes (2 and 2).

3

Example 3

Input:

n = 12

Output:

false

Note:

12 is 2 * 2 * 3. It has three prime factors, not two.

4

Example 4

Input:

n = 7

Output:

false

Note:

7 is a prime number itself. It has only one prime factor.

5

Example 5

Input:

n = 1

Output:

false

Note:

1 is not considered a semi-prime as it is not a product of two primes.

Constraints

Constraints & assumptions

  • 1 <= n <= 10^6

Out of scope

  • Highly optimized prime generation algorithms (e.g., Sieve of Eratosthenes) for very large ranges are not expected.

What interviewers evaluate

  • Correctness: The solution accurately identifies all semi-prime numbers within the given constraints.
  • Efficiency: The implementation demonstrates an appropriate time complexity for the problem's scale.
  • Code Structure: The solution is well-organized, readable, and follows good programming practices.
  • Edge Cases: Handles specific inputs like small numbers, perfect squares of primes, and prime numbers themselves correctly.

Loading editor...