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
- Define a function "gcd" that takes two positive integers, "first" and "second," as input.
- Inside the "gcd" function, check if "first" is equal to 0. If true, return "second" as the GCD.
- Otherwise, return the GCD of "second" and the remainder of "second" divided by "first" (i.e., "second % first").
- Define a function "isCoprime" that takes two positive integers, "n1" and "n2," as input.
- Inside the "isCoprime" function, print the given numbers, i.e., "Given Number (n1, n2)".
- Call the "gcd" function with "n1" and "n2" as arguments and check if the result is equal to 1.
- If the GCD is 1, print "Is co-prime," otherwise print "Is Not co-prime."
- 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
- Define the "gcd" function as given in the pseudocode.
- Define the "isCoprime" function as given in the pseudocode.
- In the main function, create an instance of the "Coprime" class.
- Test the "isCoprime" function with various pairs of numbers (e.g., (7, 2), (3, 49), and (6, 30)).
- Print the output for each test case.
Explanation with Example: Let's go through the code and the provided test cases step by step:
-
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.
-
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."
-
In the main function, we create an instance of the "Coprime" class called "task."
-
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 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);
}
}
input
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;
}
input
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;
}
input
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);
}
}
input
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();
input
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();
input
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()
input
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()
input
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);
}
}
input
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();
input
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);
}
input
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.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment