Check if a number can be represented as a sum of a Prime Number and a Perfect Square | Java 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
import java . util . * ; class GFG { static boolean isPrime ( int n ) { if ( n <= 1 ) return false ; if ( n <= 3 ) return true ; if ( n % 2 == 0 n % 3 == 0 ) return false ; for ( int i = 5 ; i * i <= n ; i = i + 6 ) { if ( n % i == 0 || n % ( i + 2 ) == 0 ) { return false ; } } return true ; } static void sumOfPrimeSquare ( int n ) { int i = 0 ; ArrayList < Integer > squares = new ArrayList < Integer > ( ) ; while ( i * i < n ) { squares . add ( i * i ) ; i ++ ; } boolean flag = false ; for ( i = 0 ; i < squares . size ( ) ; i ++ ) { int difference = n - squares . get ( i ) ; if ( isPrime ( difference ) ) { flag = true ; break ; } } if ( flag ) { System . out . print ( " Yes " ) ; } else System . out . print ( " No " ) ; } public static void main ( String [ ] args ) { int N = 27 ; sumOfPrimeSquare ( N ) ; } }