Check if an integer can be expressed as a sum of two semi | CPP Code to check if an integer can be expressed as sum of two semi - primes ; Utility function to compute semi - primes in a range ; num /= j , ++ cnt ; Increment count of prime numbers ; If number is greater than 1 , add it to the count variable as it indicates the number remain is prime number ; if count is equal to '2' then number is semi - prime ; Utility function to check if a number sum of two semi - primes ; arr [ i ] is already a semi - prime if n - arr [ i ] is also a semi - prime then we a number can be expressed as sum of two semi - primes ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000000 NEW_LINE vector < int > arr ; bool sprime [ MAX ] ; void computeSemiPrime ( ) { memset ( sprime , false , sizeof ( sprime ) ) ; for ( int i = 2 ; i < MAX ; i ++ ) { int cnt = 0 ; int num = i ; for ( int j = 2 ; cnt < 2 && j * j <= num ; ++ j ) { while ( num % j == 0 ) { } } if ( num > 1 ) ++ cnt ; if ( cnt == 2 ) { sprime [ i ] = true ; arr . push_back ( i ) ; } } } bool checkSemiPrime ( int n ) { int i = 0 ; while ( arr [ i ] <= n / 2 ) { if ( sprime [ n - arr [ i ] ] ) { return true ; } i ++ ; } return false ; } int main ( ) { computeSemiPrime ( ) ; int n = 30 ; if ( checkSemiPrime ( n ) ) cout << " YES " ; else cout << " NO " ; return 0 ; }