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.

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.

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

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.

A semiprime is a number formed by the product of two prime numbers.

For example, 6(2*3), 9(3*3), 10(2*5), 15(3*5), etc., are the semiprime numbers, and 7, 8, 12, 13, etc. are not.

Input: A positive integer N.

Output: An integer.

The questions you should ask the interviewer:

What is the constraint on N?

For example,

Input: N = 20

Output: 1

Explanation: The only pair of semiprime numbers whose sum is a prime number is (14, 15). The count is 1.

14(2*7), 15(3*5) are semiprime numbers, and 14 + 15 = 29 is prime.

Input: N = 30

Output: 8

Explanation: The pairs of semiprime numbers whose sum is a prime number are (10, 21), (14, 15), (15, 22), (15, 26), (15, 28), (20, 21), (21, 22), (21, 26). The count is 8.

Input: N = 100.

Output: 313.

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:

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

C++

#include <bits/stdc++.h>
using namespace std;

// max count of prime numbers.
const int maxN = 100000;

// Function to return the semiprime numbers in the range [1, N].
vector<int> semiPrimes(vector<int> &prime, int N)
{
// Sieve of Eratosthenes.
for (int i = 2; i <= maxN; i++) {

// If i is a prime number.
  if (prime[i] == 0) {
  for (int n = 2 * i; n <= maxN; n += i)
prime[n]++;
}
}
// Stores the semiprime numbers.
vector<int> semiPrime;

for (int i = 2; i <= N; i++){
// If i has two distinct prime factors.
if (prime[i] == 2)
semiPrime.push_back(i);
}
// return the vector of semiprime numbers.
return semiPrime;
}

// Function to count the numbers of unordered pairs of
// semiprime numbers whose sum is a prime number.
int countPairs(vector<int> semiPrime, vector<int> prime)
{
  // To store the count.
int count = 0;
int n = semiPrime.size();

  // Loop around the unordered pairs of semiprime numbers.
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// If the sum of the current pair is a prime number.
if (prime[semiPrime[i] + semiPrime[j]] == 0) {
count++;
}
}
}
  // return the final count.
return count;
}

int main()
{
int N = 50;
vector<int> prime(maxN, 0);
vector<int> semiPrime = semiPrimes(prime, N);
cout << "Number of unordered pairs are: " << countPairs(semiPrime, prime);
return 0;
}

Input: N = 50.

Output: 49.

Time Complexity: O(N²). 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(N²). Therefore, the time complexity is O(N²).

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

Also see, Euclid GCD Algorithm

FAQs

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.
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!