Check if a number can be represented as a sum of a Prime Number and a Perfect Square | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void SieveOfEratosthenes ( bool prime [ ] , int n ) { prime [ 0 ] = false ; prime [ 1 ] = false ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) { prime [ i ] = false ; } } } } void sumOfPrimeSquare ( int n ) { bool flag = false ; bool prime [ n + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; SieveOfEratosthenes ( prime , n ) ; for ( int i = 0 ; i <= n ; i ++ ) { if ( ! prime [ i ] ) continue ; int dif = n - i ; if ( ceil ( ( double ) sqrt ( dif ) ) == floor ( ( double ) sqrt ( dif ) ) ) { flag = true ; break ; } } if ( flag ) { cout << " Yes " ; } else cout << " No " ; } int main ( ) { int N = 27 ; sumOfPrimeSquare ( N ) ; return 0 ; }