Largest number less than or equal to N / 2 which is coprime to N | Function to calculate gcd of two number ; Function to check if two numbers are coprime or not ; two numbers are coprime if their gcd is 1 ; Function to find largest integer less than or equal to N / 2 and coprime with N ; Check one by one all numbers less than or equal to N / 2 ; Driver code
< ? php function gcd ( $ a , $ b ) { if ( $ b == 0 ) return $ a ; else return gcd ( $ b , $ a % $ b ) ; } function coPrime ( $ n1 , $ n2 ) { if ( gcd ( $ n1 , $ n2 ) == 1 ) return true ; else return false ; } function largestCoprime ( $ N ) { $ half = floor ( $ N / 2 ) ; while ( coPrime ( $ N , $ half ) == false ) $ half -- ; return $ half ; } $ n = 50 ; echo largestCoprime ( $ n ) ;