Mayor número menor o igual a N/2 que es coprimo de N

Dado un número N, la tarea es encontrar el entero positivo más grande menor o igual a N/2 que sea coprimo con N. 
Nota: dos números A y B se consideran coprimos si mcd(A, B) = 1. también se da que 2 < N < 10^18.
Ejemplos: 
 

Input: N = 50
Output: 23
GCD(50, 23) = 1 

Input: N = 100
Output: 49

Enfoque ingenuo: Comience desde N/2 y encuentre el número menor o igual a N/2 que es coprimo con N. 
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the above approacdh
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to calculate gcd of two number
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
// Function to check if two numbers are coprime or not
bool coPrime(ll n1, ll n2)
{
    // two numbers are coprime if their gcd is 1
    if (gcd(n1, n2) == 1)
        return true;
    else
        return false;
}
 
// Function to find largest integer less
// than or equal to N/2 and coprime with N
ll largestCoprime(ll N)
{
    ll half = floor(N / 2);
 
    // Check one by one all numbers
    // less than or equal to N/2
    while (coPrime(N, half) == false)
        half--;
 
    return half;
}
 
// Driver code
int main()
{
 
    ll n = 50;
    cout << largestCoprime(n);
 
    return 0;
}

// Java implementation of the above approacdh
import java.util.*;
 
class GFG
{
 
// Function to calculate gcd of two number
static int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
// Function to check if two
// numbers are coprime or not
static boolean coPrime(int n1, int n2)
{
    // two numbers are coprime
    // if their gcd is 1
    if (gcd(n1, n2) == 1)
        return true;
    else
        return false;
}
 
// Function to find largest integer less
// than or equal to N/2 and coprime with N
static int largestCoprime(int N)
{
    int half = (int)(N / 2);
 
    // Check one by one all numbers
    // less than or equal to N/2
    while (coPrime(N, half) == false)
        half--;
 
    return half;
}
 
// Driver code
public static void main(String args[])
{
    int n = 50;
    System.out.println(largestCoprime(n));
}
}
 
// This code is contributed by
// Surendra_Gangwar

# Python3 implementation of the above approacdh
import math as mt
 
# Function to calculate gcd of two number
def gcd( a, b):
 
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)
 
 
# Function to check if two numbers are coprime or not
def coPrime( n1, n2):
 
    # two numbers are coprime if their gcd is 1
    if (gcd(n1, n2) == 1):
        return True
    else:
        return False
 
 
# Function to find largest integer less
# than or equal to N/2 and coprime with N
def largestCoprime( N):
 
    half = mt.floor(N / 2)
 
    # Check one by one a numbers
    # less than or equal to N/2
    while (coPrime(N, half) == False):
        half -= 1
 
    return half
 
 
# Driver code
 
n = 50
print( largestCoprime(n))
 
#This code is contributed by Mohit kumar 29

// C# implementation of the above approacdh
using System;
 
class GFG
{
 
// Function to calculate gcd of two number
static int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
// Function to check if two
// numbers are coprime or not
static bool coPrime(int n1, int n2)
{
    // two numbers are coprime
    // if their gcd is 1
    if (gcd(n1, n2) == 1)
        return true;
    else
        return false;
}
 
// Function to find largest integer less
// than or equal to N/2 and coprime with N
static int largestCoprime(int N)
{
    int half = (int)(N / 2);
 
    // Check one by one all numbers
    // less than or equal to N/2
    while (coPrime(N, half) == false)
        half--;
 
    return half;
}
 
// Driver code
static void Main()
{
    int n = 50;
    Console.WriteLine(largestCoprime(n));
}
}
 
// This code is contributed by chandan_jnu

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

// Javascript implementation of the above approach
 
// Function to calculate gcd of two number
function gcd(a, b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
// Function to check if two numbers
// are coprime or not
function coPrime(n1, n2)
{
    // two numbers are coprime if
    // their gcd is 1
    if (gcd(n1, n2) == 1)
        return true;
    else
        return false;
}
 
// Function to find largest integer less
// than or equal to N/2 and coprime with N
function largestCoprime(N)
{
    let half = Math.floor(N / 2);
 
    // Check one by one all numbers
    // less than or equal to N/2
    while (coPrime(N, half) == false)
        half--;
 
    return half;
}
 
// Driver code
let n = 50;
document.write(largestCoprime(n));
 
// This code is contributed
// by gfgking

23

Complejidad de tiempo: O (nlogn)

Espacio auxiliar: O (logn)

Enfoque eficiente: para observar el patrón:
 

• Si el número dado es impar, el número coprimo más grande será (N-1)/2 .
• Si el número dado es divisible por 4, el número coprimo más grande será (N)/2 – 1 .
• Si el número dado es divisible por 2, el número coprimo más grande será (N)/2 – 2 .

Nota: Hay un caso especial 6, para el cual el mayor número coprimo menor que N / 2 será 1.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find largest integer less than
// or equal to N/2 and is coprime with N
long long largestCoprime(long long N)
{
    // Handle the case for N = 6
    if (N == 6)
        return 1;
 
    else if (N % 4 == 0)
        return (N / 2) - 1;
 
    else if (N % 2 == 0)
        return (N / 2) - 2;
 
    else
        return ((N - 1) / 2);
}
 
// Driver code
int main()
{
 
    long long int n = 50;
    cout << largestCoprime(n) << endl;
 
    return 0;
}

// Java implementation of the above approach
class GfG
{
 
    // Function to find largest integer less than
    // or equal to N/2 and is coprime with N
    static int largestCoprime(int N)
    {
         
        // Handle the case for N = 6
        if (N == 6)
            return 1;
     
        else if (N % 4 == 0)
            return (N / 2) - 1;
     
        else if (N % 2 == 0)
            return (N / 2) - 2;
     
        else
            return ((N - 1) / 2);
    }
 
    // Driver code
    public static void main(String []args)
    {
        int n = 50;
        System.out.println(largestCoprime(n));
    }
}
     
// This code is contributed by Rituraj Jain

# Python3 implementation of the above approach
 
# Function to find largest integer less than
# or equal to N/2 and is coprime with N
def largestCoprime(N):
 
    # Handle the case for N = 6
    if N == 6:
        return 1
   
    elif N % 4 == 0:
        return N // 2 - 1
   
    elif N % 2 == 0:
        return N // 2 - 2
   
    else:
        return (N - 1) // 2
 
# Driver code
if __name__ == "__main__":
   
    n = 50
    print(largestCoprime(n))
   
# This code is contributed by Rituraj Jain

// C# implementation of the above approach
using System;
 
class GfG
{
 
    // Function to find largest
    // integer less than or equal
    // to N/2 and is coprime with N
    static int largestCoprime(int N)
    {
         
        // Handle the case for N = 6
        if (N == 6)
            return 1;
     
        else if (N % 4 == 0)
            return (N / 2) - 1;
     
        else if (N % 2 == 0)
            return (N / 2) - 2;
     
        else
            return ((N - 1) / 2);
    }
 
    // Driver code
    public static void Main()
    {
        int n = 50;
        Console.WriteLine(largestCoprime(n));
    }
}
     
// This code is contributed by Ryuga

<?php
// PHP implementation of the above approach
 
// Function to find largest integer less than
// or equal to N/2 and is coprime with N
function largestCoprime($N)
{
    // Handle the case for N = 6
    if ($N == 6)
        return 1;
 
    else if ($N % 4 == 0)
        return ($N / 2) - 1;
 
    else if ($N % 2 == 0)
        return ($N / 2) - 2;
 
    else
        return (($N - 1) / 2);
}
 
// Driver code
$n = 50;
echo largestCoprime($n);
 
// This code is contributed by
// chandan_jnu
?>

<script>
 
// Javascript implementation of the approach
 
// Function to find largest integer less than
// or equal to N/2 and is coprime with N
function largestCoprime(N)
{
     
    // Handle the case for N = 6
    if (N == 6)
        return 1;
 
    else if (N % 4 == 0)
        return (N / 2) - 1;
 
    else if (N % 2 == 0)
        return (N / 2) - 2;
 
    else
        return ((N - 1) / 2);
}
 
// Driver Code
var n = 50;
 
document.write(largestCoprime(n));
 
// This code is contributed by Khushboogoyal499
     
</script>

23

Complejidad de tiempo: O(1), ya que solo hay operaciones aritméticas básicas que toman tiempo constante.

Espacio Auxiliar: O(1), ya que no se ha requerido espacio extra.