Home » ALGORITHM » ALGORITHM AND FLOWCHART FOR COPRIME NUMBER

# ALGORITHM AND FLOWCHART FOR COPRIME NUMBER

A Coprime number comes in pair of integers. Thus they are defined as those paired numbers which can be divided by the common number 1 are called coprime numbers. Suppose a and b are two positive integers and they are divisible by only 1. Then a and b are co-prime number. For example 3 and 5 are only divisible by 1. Thus 3 and 5 are co-prime number. If a and b are divisible by some more numbers other than 1 then they are not co-prime number. For example 6 and 10 are not co-prime number. Because 6 and 10 are divisible 2 also other than 1. A coprime number is also known as relatively prime and mutually prime number.

## ALGORITHM TO CHECK COPRIME NUMBER

Suppose X and Y are two Integers. We have to check that whether these two numbers are coprime numbers. A number of methods are listed below.

FIRST METHOD:

(Check Coprime Number) Let I is a counter and it is initialized from 2. F is a Boolean variable and its value is 0. In this algorithm both numbers X and Y will be divided by I simultaneously. This division process will go on till I becomes equal to variable X. If X and Y are divisible for any value of I. Then value of F is changed to 1 and the loop  will discontinue. If F is equal to 0 then X and Y are co-prime number. And if F is equal to 1 then both numbers are not co-prime.

Step 1: Start

Step 2: [ Take Inputs ] Read: X and Y

Step 3: [ Initializing Variables ] Set: I = 2 and F = 0

Step 4: Repeat While I <= X

Check If X%I == 0 AND Y%I == 0 Then

Set: F = 1 and break the loop

[ End of If Structure ]

Compute: I = I + 1

[ End of While Loop ]

Step 5: Check If F == 1 Then

Print: X and Y are Co-prime number.

Else

Print: X and Y are not Co-prime number.

Step 6: Exit

SECOND METHOD:

(Check Coprime Number) In this algorithm we will use an alternative definition of coprime number. If the GCD of two numbers is 1 then both number are co-prime. This algorithm first finds the GCD of X and Y. If GCD of X and Y is 1 then X and Y are coprime number. And if GCD of X and Y is some other value than 1 then X and Y are not coprime.

Step 1: Start

Step 2: [ Take Inputs ] Read: X and Y

Step 3: Repeat While A ≠ B

Step 3a: Check If A > B Then

Compute: A = A – B

Else

Set: Temp = A, A = B and B = Temp

Go To  Step 3a

[ End of If Else Structure ]

[ End of While Loop ]

Step 4: set: GCD = A

Step 5: Check If GCD == 1 Then

Print: A and B are Co-prime number.

Else

Print: A and B are not Co-prime number.

Step 6: Exit

FIRST METHOD:

SECOND METHOD:

### Related Posts

• ALGORITHM AND FLOWCHART FOR COMPOSITE NUMBER Those numbers which are divisible by other than itself and 1 are known as composite numbers. The number 4 can is divisible by 1, 2 and 4 therefore 4 is a composite number. But 7 is […] Posted in ALGORITHM
• ALGORITHM TO FIND GREATEST COMMON DIVISOR The GCD or greatest common divisor of two or more positive numbers is the greatest number which divides each number completely (Leaving no remainder). For example 6 and 18 are divisible by […] Posted in ALGORITHM
• ALGORITHM TO CHECK EVEN AND ODD NUMBERS A number is said to be even number if it leaves no remainder when divided by 2. There is an alternative definition of even number and it is as a number having any number from 0, 2, 4, 6 […] Posted in ALGORITHM
• PERFECT NUMBER ALGORITHM AND FLOWCHART A number is said to be a perfect number if the sum of factors of the number (excluding number itself as a factor) is equal to the number itself. Example of perfect numbers are 6, 28, 496, […] Posted in ALGORITHM