Check if an integer can be expressed as a sum of two semi | C # Code to check if an integer can be expressed as sum of two semi - primes ; Utility function to compute semi - primes in a range ; 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 is sum of two semi - primes ; arr [ i ] is already a semi - prime if n - arr [ i ] is also a semi - prime then a number can be expressed as sum of two semi - primes ; Driver code
using System . Collections . Generic ; class GFG { static int MAX = 1000000 ; static List < int > arr = new List < int > ( ) ; static bool [ ] sprime = new bool [ MAX ] ; static void computeSemiPrime ( ) { for ( int i = 0 ; i < MAX ; i ++ ) sprime [ i ] = false ; 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 ) { num /= j ; ++ cnt ; } } if ( num > 1 ) ++ cnt ; if ( cnt == 2 ) { sprime [ i ] = true ; arr . Add ( i ) ; } } } static bool checkSemiPrime ( int n ) { int i = 0 ; while ( arr [ i ] <= n / 2 ) { if ( sprime [ n - arr [ i ] ] ) { return true ; } i ++ ; } return false ; } public static void Main ( ) { computeSemiPrime ( ) ; int n = 30 ; if ( checkSemiPrime ( n ) ) System . Console . WriteLine ( " YES " ) ; else System . Console . WriteLine ( " NO " ) ; } }