Largest number less than or equal to N / 2 which is coprime to N | C ++ implementation of the above approacdh ; 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
#include <bits/stdc++.h> NEW_LINE #define ll  long long int NEW_LINE using namespace std ; ll gcd ( ll a , ll b ) { if ( b == 0 ) return a ; else return gcd ( b , a % b ) ; } bool coPrime ( ll n1 , ll n2 ) { if ( gcd ( n1 , n2 ) == 1 ) return true ; else return false ; } ll largestCoprime ( ll N ) { ll half = floor ( N / 2 ) ; while ( coPrime ( N , half ) == false ) half -- ; return half ; } int main ( ) { ll n = 50 ; cout << largestCoprime ( n ) ; return 0 ; }