Programming contests

20 Programming Exercise for Beginners

January 1, 2019 12:00 AM – December 31, 2019 12:00 AM

Relative Prime Number

Create a program that recognizes the relative prime numbers. Two numbers are relatively prime if they have no factors in common other than 1.

Input Specification

Each input line consists of two positive integers separated by a space.

Sample Input

  1. 10 12
  2. 8 9
  3. 3 3
  4. 2 3
  5. 1 1
download as text file

Output Specification

For each line, print one line to the output containing “YES” if the line contains relative primes or “NO” otherwise.

Output for Sample Input

  1. NO
  2. YES
  3. NO
  4. YES
  5. YES
download as text file

Hints and Guide

The problem can be solved by calculating the greatest common divisor of each pair of positive integers. The Euclidean algorithm based on the subtraction operation is widely known and applicable on positive integers: subtract the lower component of the pair from the greater one until the components become equal. If the algorithm stops with one, then the greatest common divisor of the original pair of positive integers is 1, hence they are relative primes.

It is recommended to create an individual gcd function that calculates the greatest common divisor of two positive integers.

One possible solution is available in: main.c.

Acknowledgement This work was supported by the construction EFOP-3.4.3-16-2016-00021. The project was supported by the European Union, co-financed by the European Social Fund.
University of Debrecen; Faculty of Informatics; v. 03/01/2019