Check whether a number is Non | Function to find prime factor and check if it is of the form 4 k + 1 or not ; 2 is a prime number but not of the form 4 k + 1 so , keep Dividing n by 2 until n is divisible by 2 ; n must be odd at this point . So we can skip one element ( Note i = i + 2 ) ; if i divides n check if i is of the form 4 k + 1 or not ; while i divides n divide n by i and update n ; This condition is to handle the case when n is a prime number greater than 2 ; Test function ; Driver code
< ? php function isNonHypotenuse ( $ n ) { while ( $ n % 2 == 0 ) { $ n = $ n / 2 ; } for ( $ i = 3 ; $ i <= sqrt ( $ n ) ; $ i = $ i + 2 ) { if ( $ n % $ i == 0 ) { if ( ( $ i - 1 ) % 4 == 0 ) return false ; while ( $ n % $ i == 0 ) { $ n = $ n / $ i ; } } } if ( $ n > 2 && ( $ n - 1 ) % 4 == 0 ) return false ; else return true ; } function test ( $ n ) { echo " Testing ▁ for ▁ " , $ n , " ▁ : ▁ " ; if ( isNonHypotenuse ( $ n ) ) echo " YES " . " STRNEWLINE " ; else echo " NO " . " STRNEWLINE " ; } $ n = 11 ; test ( $ n ) ; $ n = 10 ; test ( $ n ) ; ? >