1.
Problem
2.
Solution
3.
FAQs
4.
Key takeaways
Last Updated: Mar 27, 2024

# The Number of Unordered Pairs of Semiprime Numbers with a Prime Sum in the Range 1 to N

GAZAL ARORA
1 upvote

## Problem

Given a number N, find the count of unordered pairs of semiprime numbers in the range [1, N] such that their sum is a prime number.

Input: A positive integer N.

Output: An integer.

The questions you should ask the interviewer:

1. What is the constraint on N?

For example,

Recommended: Please try to solve it yourself before moving on to the solution.

## Solution

Idea: The idea is to use  Sieve Of Eratosthenes to maintain an array of prime numbers and then find the semiprime numbers by checking if these prime numbers have two distinct prime factors. After finding the semiprime numbers, we will count the pairs whose sum is a prime number.

Algorithm:

1. Initialize a vector prime of size N+1, and use Sieve Of Eratosthenes such that prime[i] stores distinct prime factors of i.
2. Initialize a vector semiPrime and add those prime numbers whose distinct prime factors are two.
3. Then iterate over all unordered pairs of the vector semiPrime and maintain the count of pairs whose sum is a prime number.

C++

Input: N = 50.

Output: 49.

Time Complexity: O(N2).  The time used for Sieve Of Eratosthenes is O(N), and the time used for looping around all the pairs of semiprime numbers is O(N2). Therefore, the time complexity is O(N2).

Space Complexity: O(N). These arrays use O(N) extra space: prime and semiPrime.

Also see, Euclid GCD Algorithm

## FAQs

1. What are prime numbers?
Prime Numbers are numbers greater than 1 and can be divided by 1 or itself only. For example, 2, 5, 7, 11, 13, 17, 19, 23, 29, etc, are prime numbers.

2. What are semiprime numbers?
Mathematically, a semiprime is a natural number formed by multiplying exactly two prime numbers. For example, 4, 6, 9, 10, 15, 25, 30, etc., all are semiprime numbers.

## Key takeaways

In this article, we designed an algorithm for counting the number of unordered pairs of semiprime numbers in the range [1, N], whose sum is a prime number.

We used the algorithm Sieve Of Eratosthenes to count the semiprime numbers, and then for unordered pairs of semiprime numbers, we checked if the sum is a prime number.

The algorithm's time complexity is O(N^2), whereas space complexity is O(N).
Check out this problem - Pair Sum In Array.

Don't stop here. Explore more!

Use Coding Ninjas Studio to practice various DSA questions asked in different interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.

Happy Coding!

Live masterclass