백준 2824번 : 최대공약수 C언어

https://www.acmicpc.net/problem/2824 : 백준 문제 링크

Code:

 

#include <stdio.h>
 
long long gcd(long long a, long long b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a % b);
    }
}
 
int main()
{
    int n, m;
    int a[1001] = { 0, }, b[1001] = { 0, };
    int flag = 1;
    scanf("%d", &n);
    int i, j;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
 
    }
    scanf("%d", &m);
    for (i = 0; i < m; i++)
    {
        scanf("%d", &b[i]);
    }
    long long result = 1;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            long long rdt;
            if (a[i] > b[j])
            {
                rdt = gcd(a[i], b[j]);
            }
            else
            {
                rdt = gcd(b[j], a[i]);
            }
            result *= rdt;
            a[i] /= rdt;
            b[j] /= rdt;
            if (result >= 1000000000)
            {
                {
                    result %= 1000000000;
                    flag = 0;
                }
            }
        }
    }
    
    if (flag == 1)
    {
        printf("%lld", result);
    }
    else
    {
        printf("%09lld", result);
    }
}

이 문제를 풀 때 유클리드 호제법을 이용하였다. 하지만 다른사람들 코드를 보면 에라토스테네스의 체를 이용한 분들이 많았다.