Check if two numbers are co-prime or not
Two numbers A and B are said to be Co-Prime or mutually prime if the Greatest Common Divisor of them is 1. You have been given two numbers A and B, find if they are Co-prime or not.
Examples :
Input : 2 3 Output : Co-Prime Input : 4 8 Output : Not Co-Prime
C++
// 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
// Java program to check if two // numbers are co-prime or not import java.io.*; public 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
# 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#
// 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 // 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 ?> |
Javascript
<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> |
Output
Co-Prime Not Co-Prime
Time Complexity: O(log(max(a,b)))
Auxiliary Space: O(1)
Contact Us