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
< ? php function judgeSquareSum ( $ n ) { for ( $ i = 2 ; $ i * $ i <= $ n ; $ i ++ ) { $ count = 0 ; if ( $ n % $ i == 0 ) { while ( $ n % $ i == 0 ) { $ count ++ ; $ n = ( int ) $ n / $ i ; } if ( $ i % 4 == 3 && $ count % 2 != 0 ) return false ; } } return $ n % 4 != 3 ; } $ n = 17 ; if ( judgeSquareSum ( $ n ) ) echo " Yes " ; else echo " No " ; ? >