Check whether a number can be represented by sum of two squares | Check whether a number can be represented by sum of two squares using Fermat Theorem . ; Count all the prime factors . ; Ifany prime factor of the form ( 4 k + 3 ) ( 4 k + 3 ) occurs an odd number of times . ; If n itself is a x prime number and can be expressed in the form of 4 k + 3 we return false . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool judgeSquareSum ( int n ) { for ( int i = 2 ; i * i <= n ; i ++ ) { int count = 0 ; if ( n % i == 0 ) { while ( n % i == 0 ) { count ++ ; n /= i ; } if ( i % 4 == 3 && count % 2 != 0 ) return false ; } } return n % 4 != 3 ; } int main ( ) { int n = 17 ; if ( judgeSquareSum ( n ) ) cout << " Yes " ; else cout << " No " ; }