# HackerEarth Coprimes problem solution

In this HackerEarth Coprimes problem solution, You are provided an integer n. Your task is to determine the largest integer a (a < n - 1) that is coprime of n. This implies that gcd(a,n) = 1.

## HackerEarth Coprimes problem solution.

`#include <bits/stdc++.h>typedef long double ld ;#define long long long intusing namespace std;#define mp make_pair#define pb push_back#define x first#define y secondtypedef pair<long,long> pll; const int N=1e5+1;long GCD(long a,long b){    while(a && b)    {        a=a%b;        if(a)            b=b%a;    }    return a+b;}int main(){    ios::sync_with_stdio(false);cin.tie(0);    srand(time(NULL));    int t=1;    while(t--)    {        long n;        cin>>n;        assert(3<=n && n<=1e18);        if(n&1)            cout<<n-2<<"\n";        else        {            long temp=2;            while(true)            {                long temp_gcd=GCD(n,n-temp);                if(temp_gcd==1)                {                    cout<<n-temp<<"\n";                    break;                }                temp++;            }        }    }    return 0;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 2e6 + 17; ll n;int main(){    ios::sync_with_stdio(0), cin.tie(0);    cin >> n;    if(n % 2 == 0){        for(int i = n - 3; ; i -= 2)            if(gcd(n, i) == 1){                cout << i << '\n';                break;            }    }    else        cout << n - 2 << '\n';}`