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