Check if two numbers are co-prime or not

Co-prime numbers, also known as relatively prime numbers, are a pair of positive integers whose greatest common divisor (GCD) is 1. In other words, two numbers are co-prime if they do not have any common divisor other than 1. For example, (7, 2), (3, 49), and (6, 30) are examples of pairs of numbers where each pair is co-prime. Co-prime numbers play a crucial role in number theory and various mathematical applications.

Problem Statement

Given two positive integers n1 and n2, the task is to determine whether they are co-prime or not.

Pseudocode

1. Define a function "gcd" that takes two positive integers, "first" and "second," as input.
2. Inside the "gcd" function, check if "first" is equal to 0. If true, return "second" as the GCD.
3. Otherwise, return the GCD of "second" and the remainder of "second" divided by "first" (i.e., "second % first").
4. Define a function "isCoprime" that takes two positive integers, "n1" and "n2," as input.
5. Inside the "isCoprime" function, print the given numbers, i.e., "Given Number (n1, n2)".
6. Call the "gcd" function with "n1" and "n2" as arguments and check if the result is equal to 1.
7. If the GCD is 1, print "Is co-prime," otherwise print "Is Not co-prime."
8. In the main function: a. Create an instance of the "Coprime" class called "task." b. Test the "isCoprime" function with different pairs of numbers.

Algorithm

1. Define the "gcd" function as given in the pseudocode.
2. Define the "isCoprime" function as given in the pseudocode.
3. In the main function, create an instance of the "Coprime" class.
4. Test the "isCoprime" function with various pairs of numbers (e.g., (7, 2), (3, 49), and (6, 30)).
5. Print the output for each test case.

Explanation with Example: Let's go through the code and the provided test cases step by step:

1. The "gcd" function uses the Euclidean algorithm to find the GCD of two numbers. It takes two parameters, "first" and "second," and returns the GCD.

2. The "isCoprime" function takes two numbers, "n1" and "n2," and checks if their GCD is equal to 1. If the GCD is 1, it means the numbers are co-prime, and the function prints "Is co-prime." Otherwise, it prints "Is Not co-prime."

3. In the main function, we create an instance of the "Coprime" class called "task."

4. Test cases: a. task.isCoprime(7, 2); - The GCD of 7 and 2 is 1, so the output is "Is co-prime." b. task.isCoprime(3, 49); - The GCD of 3 and 49 is also 1, so the output is "Is co-prime." c. task.isCoprime(6, 30); - The GCD of 6 and 30 is 6, so the output is "Is Not co-prime."

Code Solution

Here given code implementation process.

• Java
• C
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

/*
  Java Program 
  Check if two numbers are co-prime or not
*/
public class Coprime
{
	// Recursively find GCD of two given number
	public int gcd(int first, int second)
	{
		if (first == 0)
		{
			return second;
		}
		return gcd(second % first, first);
	}
	// Check that given two number is co prime to each other or not
	public void isCoprime(int n1, int n2)
	{
		System.out.print("\n Given Number (" + n1 + "," + n2 + ") ");
		if (gcd(n1, n2) == 1)
		{
			// When given number is co-prime
			System.out.print("\n Is co-prime ");
		}
		else
		{
			//  When given number is not co-prime
			System.out.print("\n Is Not co-prime ");
		}
	}
	public static void main(String[] args)
	{
		Coprime task = new Coprime();
		// Test Case
		task.isCoprime(7, 2);
		task.isCoprime(3, 49);
		task.isCoprime(6, 30);
	}
}

 Given Number (7,2)
 Is co-prime
 Given Number (3,49)
 Is co-prime
 Given Number (6,30)
 Is Not co-prime

// C Program
// Check if two numbers are co-prime or not
#include <stdio.h>

// Recursively find GCD of two given number
int find_gcd(int first, int second)
{
	if (first == 0)
	{
		return second;
	}
	return find_gcd(second % first, first);
}
// Check that given two number is co prime to each other or not
void isCoprime(int n1, int n2)
{
	printf("\n Given Number (%d %d)  ", n1, n2);
	if (find_gcd(n1, n2) == 1)
	{
		// When given number is co-prime
		printf("\n Is co-prime ");
	}
	else
	{
		//  When given number is not co-prime
		printf("\n Is Not co-prime ");
	}
}
int main()
{
	// Test Case
	isCoprime(7, 2);
	isCoprime(3, 49);
	isCoprime(6, 30);
	return 0;
}

 Given Number (7 2)
 Is co-prime
 Given Number (3 49)
 Is co-prime
 Given Number (6 30)
 Is Not co-prime

// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program 
  Check if two numbers are co-prime or not
*/
class Coprime
{
	public:
		// Recursively find GCD of two given number
		int gcd(int first, int second)
		{
			if (first == 0)
			{
				return second;
			}
			return this->gcd(second % first, first);
		}
	// Check that given two number is co prime to each other or not
	void isCoprime(int n1, int n2)
	{
		cout << "\n Given Number (" << n1 << "," << n2 << ") ";
		if (this->gcd(n1, n2) == 1)
		{
			// When given number is co-prime
			cout << "\n Is co-prime ";
		}
		else
		{
			//  When given number is not co-prime
			cout << "\n Is Not co-prime ";
		}
	}
};
int main()
{
	Coprime *task = new Coprime();
	// Test Case
	task->isCoprime(7, 2);
	task->isCoprime(3, 49);
	task->isCoprime(6, 30);
	return 0;
}

 Given Number (7,2)
 Is co-prime
 Given Number (3,49)
 Is co-prime
 Given Number (6,30)
 Is Not co-prime

// Include namespace system
using System;
/*
  Csharp Program 
  Check if two numbers are co-prime or not
*/
public class Coprime
{
	// Recursively find GCD of two given number
	public int gcd(int first, int second)
	{
		if (first == 0)
		{
			return second;
		}
		return this.gcd(second % first, first);
	}
	// Check that given two number is co prime to each other or not
	public void isCoprime(int n1, int n2)
	{
		Console.Write("\n Given Number (" + n1 + "," + n2 + ") ");
		if (this.gcd(n1, n2) == 1)
		{
			// When given number is co-prime
			Console.Write("\n Is co-prime ");
		}
		else
		{
			//  When given number is not co-prime
			Console.Write("\n Is Not co-prime ");
		}
	}
	public static void Main(String[] args)
	{
		Coprime task = new Coprime();
		// Test Case
		task.isCoprime(7, 2);
		task.isCoprime(3, 49);
		task.isCoprime(6, 30);
	}
}

 Given Number (7,2)
 Is co-prime
 Given Number (3,49)
 Is co-prime
 Given Number (6,30)
 Is Not co-prime

<?php
/*
  Php Program 
  Check if two numbers are co-prime or not
*/
class Coprime
{
	// Recursively find GCD of two given number
	public
	function gcd($first, $second)
	{
		if ($first == 0)
		{
			return $second;
		}
		return $this->gcd($second % $first, $first);
	}
	// Check that given two number is co prime to each other or not
	public
	function isCoprime($n1, $n2)
	{
		echo "\n Given Number (". $n1 .",". $n2 .") ";
		if ($this->gcd($n1, $n2) == 1)
		{
			// When given number is co-prime
			echo "\n Is co-prime ";
		}
		else
		{
			//  When given number is not co-prime
			echo "\n Is Not co-prime ";
		}
	}
}

function main()
{
	$task = new Coprime();
	// Test Case
	$task->isCoprime(7, 2);
	$task->isCoprime(3, 49);
	$task->isCoprime(6, 30);
}
main();

 Given Number (7,2)
 Is co-prime
 Given Number (3,49)
 Is co-prime
 Given Number (6,30)
 Is Not co-prime

/*
  Node JS Program 
  Check if two numbers are co-prime or not
*/
class Coprime
{
	// Recursively find GCD of two given number
	gcd(first, second)
	{
		if (first == 0)
		{
			return second;
		}
		return this.gcd(second % first, first);
	}
	// Check that given two number is co prime to each other or not
	isCoprime(n1, n2)
	{
		process.stdout.write("\n Given Number (" + n1 + "," + n2 + ") ");
		if (this.gcd(n1, n2) == 1)
		{
			// When given number is co-prime
			process.stdout.write("\n Is co-prime ");
		}
		else
		{
			//  When given number is not co-prime
			process.stdout.write("\n Is Not co-prime ");
		}
	}
}

function main()
{
	var task = new Coprime();
	// Test Case
	task.isCoprime(7, 2);
	task.isCoprime(3, 49);
	task.isCoprime(6, 30);
}
main();

 Given Number (7,2)
 Is co-prime
 Given Number (3,49)
 Is co-prime
 Given Number (6,30)
 Is Not co-prime

# Python 3 Program
# Check if two numbers are co - prime or not
class Coprime :
	# Recursively find GCD of two given number
	def gcd(self, first, second) :
		if (first == 0) :
			return second
		
		return self.gcd(second % first, first)
	
	# Check that given two number is co prime to each other or not
	def isCoprime(self, n1, n2) :
		print("\n Given Number (", n1 ,",", n2 ,") ", end = "")
		if (self.gcd(n1, n2) == 1) :
			# When given number is co - prime
			print("\n Is co-prime ", end = "")
		else :
			# When given number is not co - prime
			print("\n Is Not co-prime ", end = "")
		
	

def main() :
	task = Coprime()
	# Test Case
	task.isCoprime(7, 2)
	task.isCoprime(3, 49)
	task.isCoprime(6, 30)

if __name__ == "__main__": main()

 Given Number ( 7 , 2 )
 Is co-prime
 Given Number ( 3 , 49 )
 Is co-prime
 Given Number ( 6 , 30 )
 Is Not co-prime

# Ruby Program
# Check if two numbers are co - prime or not
class Coprime 
	# Recursively find GCD of two given number
	def gcd(first, second) 
		if (first == 0) 
			return second
		end

		return self.gcd(second % first, first)
	end

	# Check that given two number is co prime to each other or not
	def isCoprime(n1, n2) 
		print("\n Given Number (", n1 ,",", n2 ,") ")
		if (self.gcd(n1, n2) == 1) 
			# When given number is co - prime
			print("\n Is co-prime ")
		else 
			# When given number is not co - prime
			print("\n Is Not co-prime ")
		end

	end

end

def main() 
	task = Coprime.new()
	# Test Case
	task.isCoprime(7, 2)
	task.isCoprime(3, 49)
	task.isCoprime(6, 30)
end

main()

 Given Number (7,2) 
 Is co-prime 
 Given Number (3,49) 
 Is co-prime 
 Given Number (6,30) 
 Is Not co-prime 

/*
  Scala Program 
  Check if two numbers are co-prime or not
*/
class Coprime
{
	// Recursively find GCD of two given number
	def gcd(first: Int, second: Int): Int = {
		if (first == 0)
		{
			return second;
		}
		return gcd(second % first, first);
	}
	// Check that given two number is co prime to each other or not
	def isCoprime(n1: Int, n2: Int): Unit = {
		print("\n Given Number (" + n1 + "," + n2 + ") ");
		if (gcd(n1, n2) == 1)
		{
			// When given number is co-prime
			print("\n Is co-prime ");
		}
		else
		{
			//  When given number is not co-prime
			print("\n Is Not co-prime ");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Coprime = new Coprime();
		// Test Case
		task.isCoprime(7, 2);
		task.isCoprime(3, 49);
		task.isCoprime(6, 30);
	}
}

 Given Number (7,2)
 Is co-prime
 Given Number (3,49)
 Is co-prime
 Given Number (6,30)
 Is Not co-prime

/*
  Swift 4 Program 
  Check if two numbers are co-prime or not
*/
class Coprime
{
	// Recursively find GCD of two given number
	func gcd(_ first: Int, _ second: Int)->Int
	{
		if (first == 0)
		{
			return second;
		}
		return self.gcd(second % first, first);
	}
	// Check that given two number is co prime to each other or not
	func isCoprime(_ n1: Int, _ n2: Int)
	{
		print("\n Given Number (", n1 ,",", n2 ,") ", terminator: "");
		if (self.gcd(n1, n2) == 1)
		{
			// When given number is co-prime
			print("\n Is co-prime ", terminator: "");
		}
		else
		{
			//  When given number is not co-prime
			print("\n Is Not co-prime ", terminator: "");
		}
	}
}
func main()
{
	let task: Coprime = Coprime();
	// Test Case
	task.isCoprime(7, 2);
	task.isCoprime(3, 49);
	task.isCoprime(6, 30);
}
main();

 Given Number ( 7 , 2 )
 Is co-prime
 Given Number ( 3 , 49 )
 Is co-prime
 Given Number ( 6 , 30 )
 Is Not co-prime

/*
  Kotlin Program 
  Check if two numbers are co-prime or not
*/
class Coprime
{
	// Recursively find GCD of two given number
	fun gcd(first: Int, second: Int): Int
	{
		if (first == 0)
		{
			return second;
		}
		return this.gcd(second % first, first);
	}
	// Check that given two number is co prime to each other or not
	fun isCoprime(n1: Int, n2: Int): Unit
	{
		print("\n Given Number (" + n1 + "," + n2 + ") ");
		if (this.gcd(n1, n2) == 1)
		{
			// When given number is co-prime
			print("\n Is co-prime ");
		}
		else
		{
			//  When given number is not co-prime
			print("\n Is Not co-prime ");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Coprime = Coprime();
	// Test Case
	task.isCoprime(7, 2);
	task.isCoprime(3, 49);
	task.isCoprime(6, 30);
}

 Given Number (7,2)
 Is co-prime
 Given Number (3,49)
 Is co-prime
 Given Number (6,30)
 Is Not co-prime

Output Explanation

For the test cases provided:

• (7, 2) are co-prime because their GCD is 1.
• (3, 49) are co-prime because their GCD is 1.
• (6, 30) are not co-prime because their GCD is 6.

Time Complexity

The time complexity of the given code is determined mainly by the Euclidean algorithm used to find the GCD of two numbers. The time complexity of the Euclidean algorithm is O(log(min(n1, n2))). Since the Euclidean algorithm is called recursively, the overall time complexity of the code remains O(log(min(n1, n2))).

In conclusion, the provided code correctly determines whether two given numbers are co-prime or not using the Euclidean algorithm to find their GCD. The code has been tested with sample inputs, and the output for each test case matches the expected results.