Problem Set2(Coprimes)

1. Given two numbers ‘m’ and ‘n’, design an algorithm and write the Python code to check if they are relatively prime. Two integers ‘a’ and ‘b’ are said to be relatively prime, mutually prime, or coprime, if the only positive integer that divides both of them is 1. For example, 14 and 15 are coprime since the factors of 14 are 1, 2, 7, & 14 and factors of 15 are 1, 3, 5, & 15 and there is no common factor other than 1. (Use only conditional and iterational statements for designing the algorithm and implementation).

Input

Get the numbers m,n



Processing Involved

initialize factor as 1

initialize i as 1

if m is less than n then let min = m

else min = m

while factor is equal to 1 and i is less than or equal to min

if m % i is equal to 0 and n%i is equal to 0 then

factor is equal to i

outside if

i = i +1



Output

if factor is not equal to 1 then display that the two given numbers are not co-prime

else if factor is 1 then display the given numbers are coprime

Algorithm:

Step1. Get the numbers m,n

Step2. initialize factor as 1 and i as 1

Step3. find if m is smaller than n if yes then let min as m else assign min as n

Step4. Repeat while factor is equal to 1 and i is less than or equal to min

Step4.1 check if m % i is equal to 0 and n%i is equal to 0 then factor is equal to i

Step4.2 i = i +1

Step5. if factor is 1 then display the two numbers are coprimes else display that the two numbers are not coprimes

Step6. End

Program:

Program:
	m = eval(input())
	n = eval(input())
	i = 1
	factor = 1
	if m >= n:
	min = n
	else:
	min = m
	while i <= min and factor == 1:
	if m%i==0 and n%i == 0:
	factor = i
	i += 1
	if factor == 1:
	print("Coprime")
	else:
	print("Not coprime")

Flowchart



To edit the flowchart click on this