C bootcamp · Lab 28

Greatest common divisor

mediumFunctions12 minLesson: Functions

← Prime checkAll labsStar triangle →

Read the question, write C on the right, then Run or Check.

QuestionHint and solution stay closed until you open them

Read two positive integers and print their greatest common divisor.

Euclid: while b is not 0, replace (a, b) with (b, a % b). Then a is the gcd.

Input. Two integers a and b.

Output. One integer: gcd(a, b).

Constraints

  • 1 ≤ a, b ≤ 1 000 000

Examples

Example 1
Input
48 18
Output
6
Example 2
Input
7 13
Output
1
Hint
  1. int t = b; b = a % b; a = t; inside a while (b != 0) loop.
  2. You can also write a recursive function.
Show correct code

Peek only after you have tried. You can still Check your own version.

#include <stdio.h>

int main(void) {
  int a, b;
  if (scanf("%d %d", &a, &b) != 2) return 1;
  while (b != 0) {
    int t = b;
    b = a % b;
    a = t;
  }
  printf("%d\n", a);
  return 0;
}
main.cC17 · gcc · Ctrl + Enter runs
ResultIdle
Run to see output. Check grades the tests.