Count of unordered pairs of semi-prime numbers with prime sum in range [1, N] - Coding

Given a positive integer N, the task is to find the number of unordered pairs of semi-prime numbers in the range [1, N] such that their sum is prime.

Examples:

Input: N = 25
Output: 5
Explanation:
The valid pairs of semi-prime numbers whose sum is also prime are (10, 21), (14, 15), (15, 22), (20, 21), and (21, 22). The count of such numbers is 5.

Input: N = 100
Output: 313

Approach: The given problem can be solved by using the Sieve of Eratosthenes. An array prime[] can be created where prime[i] stores the distinct prime factors of the number using the Sieve. All numbers in the range [1, N] with 2 distinct prime factors can be stored in a vector semiPrimes. Thereafter, iterate over all unordered pairs of the vector semiPrimes and maintain the count of pairs with prime sum.

Below is the implementation of the above approach:

C++

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 100000;
 
// Stores the count of distinct prime
// number in factor of current number
int prime[maxn] = {};
 
// Function to return the vector of
// semi prime numbers in range [1, N]
vector<int> semiPrimes(int N)
{
    // Count of distinct prime number
    // in the factor of current number
    // using Sieve of Eratosthenes
    for (int p = 2; p <= maxn; p++) {
 
        // If current number is prime
        if (prime[p] == 0) {
            for (int i = 2 * p; i <= maxn; i += p)
                prime[i]++;
        }
    }
 
    // Stores the semi prime numbers
    vector<int> sPrimes;
 
    for (int p = 2; p <= N; p++)
 
        // If p has 2 distinct prime factors
        if (prime[p] == 2)
            sPrimes.push_back(p);
 
    // Return vector
    return sPrimes;
}
 
// Function to count unordered pairs of
// semi prime numbers with prime sum
int countPairs(vector<int> semiPrimes)
{
    // Stores the final count
    int cnt = 0;
 
    // Loop to iterate over all the
    // l unordered pairs
    for (int i = 0;
         i < semiPrimes.size(); i++) {
        for (int j = i + 1;
             j < semiPrimes.size(); j++) {
 
            // If sum of current semi prime
            // numbers is a prime number
            if (prime[semiPrimes[i]
                      + semiPrimes[j]]
                == 0) {
                cnt++;
            }
        }
    }
 
    // Return answer
    return cnt;
}
 
// Driver Code
int main()
{
    int N = 100;
    cout << countPairs(semiPrimes(N));
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
    static int maxn = 100000;
 
    // Stores the count of distinct prime
    // number in factor of current number
    static int[] prime = new int[maxn + 1];
 
    // Function to return the vector of
    // semi prime numbers in range [1, N]
    static ArrayList<Integer> semiPrimes(int N)
    {
       
        // Count of distinct prime number
        // in the factor of current number
        // using Sieve of Eratosthenes
        for (int p = 2; p <= maxn; p++) {
 
            // If current number is prime
            if (prime[p] == 0) {
                for (int i = 2 * p; i <= maxn; i += p)
                    prime[i]++;
            }
        }
 
        // Stores the semi prime numbers
        ArrayList<Integer> sPrimes
            = new ArrayList<Integer>();
 
        for (int p = 2; p <= N; p++)
 
            // If p has 2 distinct prime factors
            if (prime[p] == 2)
                sPrimes.add(p);
 
        // Return vector
        return sPrimes;
    }
 
    // Function to count unordered pairs of
    // semi prime numbers with prime sum
    static int countPairs(ArrayList<Integer> semiPrimes)
    {
       
        // Stores the final count
        int cnt = 0;
 
        // Loop to iterate over all the
        // l unordered pairs
        for (int i = 0; i < semiPrimes.size(); i++) {
            for (int j = i + 1; j < semiPrimes.size(); j++) {
 
                // If sum of current semi prime
                // numbers is a prime number
                if (prime[semiPrimes.get(i) + semiPrimes.get(j)] == 0) {
                    cnt++;
                }
            }
        }
 
        // Return answer
        return cnt;
    }
 
// Driver Code
public static void main(String[] args)
{
    int N = 100;
    System.out.print(countPairs(semiPrimes(N)));
}
}
 
// This code is contributed by code_hunt.

Python3

# python program of the above approach
 
maxn = 100000
 
# Stores the count of distinct prime
# number in factor of current number
prime = [0 for _ in range(maxn)]
 
# Function to return the vector of
# semi prime numbers in range [1, N]
 
 
def semiPrimes(N):
 
    # Count of distinct prime number
    # in the factor of current number
    # using Sieve of Eratosthenes
    for p in range(2, maxn):
 
        # If current number is prime
        if (prime[p] == 0):
            for i in range(2*p, maxn, p):
                prime[i] += 1
 
    # Stores the semi prime numbers
    sPrimes = []
 
    for p in range(2, N+1):
 
        # If p has 2 distinct prime factors
        if (prime[p] == 2):
            sPrimes.append(p)
 
    # Return vector
    return sPrimes
 
 
# Function to count unordered pairs of
# semi prime numbers with prime sum
def countPairs(semiPrimes):
 
    # Stores the final count
    cnt = 0
 
    # Loop to iterate over all the
    # l unordered pairs
    for i in range(0, len(semiPrimes)):
        for j in range(i+1, len(semiPrimes)):
 
            # If sum of current semi prime
            # numbers is a prime number
            if (prime[semiPrimes[i] + semiPrimes[j]] == 0):
                cnt += 1
 
    # Return answer
    return cnt
 
 
# Driver Code
if __name__ == "__main__":
 
    N = 100
    print(countPairs(semiPrimes(N)))
 
# This code is contributed by rakeshsahni

C#

// C# program of the above approach
using System;
using System.Collections.Generic;
class GFG {
    const int maxn = 100000;
 
    // Stores the count of distinct prime
    // number in factor of current number
    static int[] prime = new int[maxn + 1];
 
    // Function to return the vector of
    // semi prime numbers in range [1, N]
    static List<int> semiPrimes(int N)
    {
        // Count of distinct prime number
        // in the factor of current number
        // using Sieve of Eratosthenes
        for (int p = 2; p <= maxn; p++) {
 
            // If current number is prime
            if (prime[p] == 0) {
                for (int i = 2 * p; i <= maxn; i += p)
                    prime[i]++;
            }
        }
 
        // Stores the semi prime numbers
        List<int> sPrimes = new List<int>();
 
        for (int p = 2; p <= N; p++)
 
            // If p has 2 distinct prime factors
            if (prime[p] == 2)
                sPrimes.Add(p);
 
        // Return vector
        return sPrimes;
    }
 
    // Function to count unordered pairs of
    // semi prime numbers with prime sum
    static int countPairs(List<int> semiPrimes)
    {
        // Stores the final count
        int cnt = 0;
 
        // Loop to iterate over all the
        // l unordered pairs
        for (int i = 0; i < semiPrimes.Count; i++) {
            for (int j = i + 1; j < semiPrimes.Count; j++) {
 
                // If sum of current semi prime
                // numbers is a prime number
                if (prime[semiPrimes[i] + semiPrimes[j]]
                    == 0) {
                    cnt++;
                }
            }
        }
 
        // Return answer
        return cnt;
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 100;
        Console.WriteLine(countPairs(semiPrimes(N)));
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
 
 
        const maxn = 100000;
 
        // Stores the count of distinct prime
        // number in factor of current number
        let prime = new Array(maxn).fill(0);
 
        // Function to return the vector of
        // semi prime numbers in range [1, N]
        function semiPrimes(N) {
            // Count of distinct prime number
            // in the factor of current number
            // using Sieve of Eratosthenes
            for (let p = 2; p <= maxn; p++) {
 
                // If current number is prime
                if (prime[p] == 0) {
                    for (let i = 2 * p; i <= maxn; i += p)
                        prime[i]++;
                }
            }
 
            // Stores the semi prime numbers
            let sPrimes = [];
 
            for (let p = 2; p <= N; p++)
 
                // If p has 2 distinct prime factors
                if (prime[p] == 2)
                    sPrimes.push(p);
 
            // Return vector
            return sPrimes;
        }
 
        // Function to count unordered pairs of
        // semi prime numbers with prime sum
        function countPairs(semiPrimes) {
            // Stores the final count
            let cnt = 0;
 
            // Loop to iterate over all the
            // l unordered pairs
            for (let i = 0;
                i < semiPrimes.length; i++) {
                for (let j = i + 1;
                    j < semiPrimes.length; j++) {
 
                    // If sum of current semi prime
                    // numbers is a prime number
                    if (prime[semiPrimes[i]
                        + semiPrimes[j]]
                        == 0) {
                        cnt++;
                    }
                }
            }
 
            // Return answer
            return cnt;
        }
 
        // Driver Code
 
        let N = 100;
        document.write(countPairs(semiPrimes(N)));
 
 
// This code is contributed by Potta Lokesh
    </script>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Find permutation of numbers upto N with a specific sum in a specific range
Count of triplets till N whose product is at most N
Count of Unique Direct Path Between N Points On a Plane
Check if elements of given array can be rearranged such that (arr[i] + i*K) % N = i for all values of i in range [0, N-1]
Count of distinct integers belonging to first N terms of at least one of given GPs

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	13