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,
1. 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. 2. 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. 3. 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>

Input: N = 50.
Output: 49.
Time Complexity: O(N^{2}). 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^{2}). Therefore, the time complexity is O(N^{2}).
Space Complexity: O(N). These arrays use O(N) extra space: prime and semiPrime.
Also see, Euclid GCD Algorithm