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 numberint 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 sumint 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 Codeint main(){ int N = 100; cout << countPairs(semiPrimes(N)); return 0;} |
Java
// Java program for the above approachimport 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 Codepublic 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 approachmaxn = 100000# Stores the count of distinct prime# number in factor of current numberprime = [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 sumdef 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 Codeif __name__ == "__main__": N = 100 print(countPairs(semiPrimes(N)))# This code is contributed by rakeshsahni |
C#
// C# program of the above approachusing 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:
313
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
