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 check if a number is prime or not ; Base Cases ; Check if n is divisible by 2 or 3 ; Iterate over every 6 number from the range [ 5 , sqrt ( N ) ] ; If n is found to be non - prime ; Otherwise , return true ; Function to check if a number can be represented as the sum of a prime number and a perfect square or not ; Stores all perfect squares less than N ; Store the perfect square in the array ; Iterate over all perfect squares ; Store the difference of perfect square from n ; If difference is prime ; Update flag ; Break out of the loop ; If N is the sum of a prime number and a perfect square ; Driver Code
from math import sqrt NEW_LINE def isPrime ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n <= 3 ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( n % 2 == 0 or n % 3 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT for i in range ( 5 , int ( sqrt ( n ) ) + 1 , 6 ) : NEW_LINE INDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def sumOfPrimeSquare ( n ) : NEW_LINE INDENT i = 0 NEW_LINE squares = [ ] NEW_LINE while ( i * i < n ) : NEW_LINE INDENT squares . append ( i * i ) NEW_LINE i += 1 NEW_LINE DEDENT flag = False NEW_LINE for i in range ( len ( squares ) ) : NEW_LINE INDENT difference = n - squares [ i ] NEW_LINE if ( isPrime ( difference ) ) : 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