Check if an integer can be expressed as a sum of two semi | Python3 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 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
MAX = 10000 NEW_LINE arr = [ ] NEW_LINE sprime = [ False ] * ( MAX ) NEW_LINE def computeSemiPrime ( ) : NEW_LINE INDENT for i in range ( 2 , MAX ) : NEW_LINE INDENT cnt , num , j = 0 , i , 2 NEW_LINE while cnt < 2 and j * j <= num : NEW_LINE INDENT while num % j == 0 : NEW_LINE INDENT num /= j NEW_LINE cnt += 1 NEW_LINE DEDENT j += 1 NEW_LINE DEDENT if num > 1 : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT if cnt == 2 : NEW_LINE INDENT sprime [ i ] = True NEW_LINE arr . append ( i ) NEW_LINE DEDENT DEDENT DEDENT def checkSemiPrime ( n ) : NEW_LINE INDENT i = 0 NEW_LINE while arr [ i ] <= n // 2 : NEW_LINE INDENT if sprime [ n - arr [ i ] ] == True : NEW_LINE INDENT return True NEW_LINE DEDENT i += 1 NEW_LINE DEDENT return False NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT computeSemiPrime ( ) NEW_LINE n = 30 NEW_LINE if checkSemiPrime ( n ) == True : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT