Comprobar si dos números son coprimos o no

Se dice que dos números A y B son coprimos o primos entre sí si el máximo común divisor de ellos es 1. Te han dado dos números A y B, averigua si son coprimos o no.
Ejemplos: 
 

Input : 2 3
Output : Co-Prime

Input : 4 8
Output : Not Co-Prime

// CPP program to check if two
// numbers are co-prime or not
#include<bits/stdc++.h>
using namespace std;
 
// function to check and print if
// two numbers are co-prime or not
void coprime(int a, int b) {
     
    if ( __gcd(a, b) == 1)
        cout << "Co-Prime" << endl;
    else
        cout << "Not Co-Prime" << endl;       
}
 
// driver code
int main()
{
    int a = 5, b = 6;
    coprime(a, b);   
    a = 8, b = 16;
    coprime(a, b);       
    return 0;
}

// Java program to check if two
// numbers are co-prime or not
class GFG {
     
    // Recursive function to
    // return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0 || b == 0)
            return 0;
         
        // base case
        if (a == b)
            return a;
         
        // a is greater
        if (a > b)
            return __gcd(a-b, b);
                 
        return __gcd(a, b-a);
    }
     
    // function to check and print if
    // two numbers are co-prime or not
    static void coprime(int a, int b) {
         
        if ( __gcd(a, b) == 1)
            System.out.println("Co-Prime");
        else
            System.out.println("Not Co-Prime");    
    }
     
    //driver code
    public static void main (String[] args)
    {
        int a = 5, b = 6;
        coprime(a, b);
         
        a = 8; b = 16;
        coprime(a, b);
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to check if two
# numbers are co-prime or not
 
# Recursive function to
# return gcd of a and b
def __gcd(a, b):
 
    # Everything divides 0
    if (a == 0 or b == 0): return 0
     
    # base case
    if (a == b): return a
     
    # a is greater
    if (a > b):
        return __gcd(a - b, b)
             
    return __gcd(a, b - a)
 
# Function to check and print if
# two numbers are co-prime or not
def coprime(a, b):
     
    if ( __gcd(a, b) == 1):
        print("Co-Prime")
    else:
        print("Not Co-Prime")    
 
# Driver code
a = 5; b = 6
coprime(a, b)
 
a = 8; b = 16
coprime(a, b)
 
# This code is contributed by Anant Agarwal

// C# program to check if two
// numbers are co-prime or not
using System;
 
class GFG {
 
    // Recursive function to
    // return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0 || b == 0)
            return 0;
 
        // base case
        if (a == b)
            return a;
 
        // a is greater
        if (a > b)
            return __gcd(a - b, b);
 
        return __gcd(a, b - a);
    }
 
    // function to check and print if
    // two numbers are co-prime or not
    static void coprime(int a, int b) {
 
        if (__gcd(a, b) == 1)
            Console.WriteLine("Co-Prime");
        else
            Console.WriteLine("Not Co-Prime");
    }
 
    // Driver code
    public static void Main()
    {
        int a = 5, b = 6;
        coprime(a, b);
        a = 8;
        b = 16;
        coprime(a, b);
    }
}
 
// This code is contributed by Anant Agarwal.

<?php
// PHP program to check if two
// numbers are co-prime or not
 
// Recursive function to
// return gcd of a and b
function __gcd($a, $b)
    {
        // Everything divides 0
        if ($a == 0 || $b == 0)
            return 0;
 
        // base case
        if ($a == $b)
            return $a;
 
        // a is greater
        if ($a > $b)
            return __gcd($a - $b, $b);
 
        return __gcd($a, $b - $a);
    }
 
    // function to check and print if
    // two numbers are co-prime or not
function coprime($a, $b)
{
    if (__gcd($a, $b) == 1)
        echo "Co-Prime","\n";
    else
        echo "Not Co-Prime","\n";
}
 
// Driver Code
$a = 5; $b = 6;
coprime($a, $b);
$a = 8;
$b = 16;
coprime($a, $b);
 
// This code is contributed by aj_36
?>

<script>
 
// Javascript program to check if two
// numbers are co-prime or not
 
// Recursive function to
// return gcd of a and b
function __gcd(a, b)
{
     
    // Everything divides 0
    if (a == 0 || b == 0)
        return 0;
     
    // Base case
    if (a == b)
        return a;
     
    // a is greater
    if (a > b)
        return __gcd(a - b, b);
             
    return __gcd(a, b - a);
}
 
// Function to check and print if
// two numbers are co-prime or not
function coprime(a, b)
{
    if (__gcd(a, b) == 1)
        document.write("Co-Prime" + "<br>");
    else
        document.write("Not Co-Prime");    
}
 
 
// Driver Code
var a = 5, b = 6;
coprime(a, b);
 
a = 8; b = 16;
coprime(a, b);
 
// This code is contributed by Kirti
 
</script>

Producción : 

Co-Prime
Not Co-Prime

Complejidad del tiempo: O(log(max(a,b)))

Espacio Auxiliar: O(1)

Este artículo es una contribución de Dibyendu Roy Chaudhuri . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.