Check if a number can be represented as a sum of a Prime Number and a Perfect Square | Python3 program for the above approach ; Function to store all prime numbers less than or equal to N ; Update prime [ 0 ] and prime [ 1 ] as false ; Iterate over the range [ 2 , sqrt ( N ) ] ; If p is a prime ; Update all multiples of p which are <= n as non - prime ; Function to check whether a number can be represented as the sum of a prime number and a perfect square ; Stores all the prime numbers less than or equal to n ; Update the array prime [ ] ; Iterate over the range [ 0 , n ] ; If current number is non - prime ; Update difference ; If difference is a perfect square ; If true , update flag and break out of loop ; If N can be expressed as sum of prime number and perfect square ; Driver Code
import math NEW_LINE def SieveOfEratosthenes ( prime , n ) : NEW_LINE INDENT prime [ 0 ] = False NEW_LINE prime [ 1 ] = False NEW_LINE for p in range ( 2 , int ( n ** ( 1 / 2 ) ) ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p ** 2 , n + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT def sumOfPrimeSquare ( n ) : NEW_LINE INDENT flag = False NEW_LINE prime = [ True ] * ( n + 1 ) NEW_LINE SieveOfEratosthenes ( prime , n ) NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT if ( not prime [ i ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT dif = n - i NEW_LINE if ( math . ceil ( dif ** ( 1 / 2 ) ) == math . floor ( dif ** ( 1 / 2 ) ) ) : NEW_LINE INDENT flag = True NEW_LINE break NEW_LINE DEDENT DEDENT if ( flag ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 27 NEW_LINE sumOfPrimeSquare ( N ) NEW_LINE DEDENT