c 언어 최대 공약수

구차 판정 법.
만약 두 수의 차이 가 크 지 않 으 면 대수 로 소 수 를 줄 일 수 있다. 소득 의 차이 와 소수 의 최대 공약 수 는 원래 두 수의 최대 공약 수 이다. 예 를 들 어 78 과 60 의 최대 공약 수 를 구 하 는 것 이다. 78 - 60 = 18, 18 과 60 의 최대 공약 수 는 6 이기 때문에 78 과 60 의 최대 공약 수 는 6 이다.
만약 두 수의 차이 가 비교적 크다 면 대수 로 소수 의 몇 배 를 줄 이 고 소수 보다 작 을 때 까지 줄 일 수 있다. 차이 와 소수 의 최대 공 약 수 는 원래 두 수의 최대 공 약수 이다. 예 를 들 어 92 와 16 의 최대 공 약수. 92 - 16 = 76, 76 - 16 = 60, 60 - 16 = 44, 44 - 16 = 28, 28 - 16 = 12, 12 와 16 의 최대 공 약 수 는 4 이다.그래서 92 와 16 의 최대 공 약수 가 4 입 니 다.
전전 상 제법.
두 개의 수가 비교적 클 때, 전전 상 제법 을 사용 하 는 것 이 비교적 편리 하 다. 그 방법 은:
소수 로 대 수 를 나 누 면 소 수 는 원 하 는 최대 공약수 이다. 그렇지 않 으 면 나머지 로 아까 의 나 누 기 를 나눈다.이 새로운 나눗셈 의 나머지 로 아까 의 나머지 를 제거 합 니 다. 이러한 유추 에 따 르 면 하나의 나눗셈 이 정 리 될 때 까지 이 때 나 누 는 숫자 로 서 원 하 는 최대 공약수 입 니 다.
예 를 들 어 4453 과 5767 의 최대 공약수 를 구 할 때 다음 과 같은 나눗셈 을 할 수 있다.
5767 ÷ 4453 = 1 여 1314
4453 ÷ 1314 = 3 여 511
1314 ÷ 511 = 2 여 292
511 ÷ 292 = 1 여 219
292 ÷ 219 = 1 여 73
　　219÷73＝3
그래서 5767 과 4453 의 최대 공약수 가 73 이라는 것 을 알 게 되 었 다.
전전 상 나눗셈 은 적용 이 비교적 넓 고 짧 은 나눗셈 보다 훨씬 좋 으 며, 임의의 두 수의 최대 공약수 를 구 할 수 있다.
초등학교 수학 을 복습 한 후, 먼저 두 개의 수 를 재 귀판 으로 하 자.

int GetGCDRec(int n, int m)
{
   if (m < n)
    {
        m ^= n;
        n ^= m;
        m ^= n;
    }

    if (n == 0)
        return m;
    else
        return GetGCDRec(n, m % n);
}

전전 상 제법 으로 한 수조 의 모든 수의 최대 공약수 를 구하 다

int GetGCD(int *arr, int len)
{
    int iMax = arr[0], iCurr, iRemainder;

    for(int i = 1; i < len; i++)
    {
        iCurr = arr[i];

        if (iMax < iCurr)
        {
            iMax ^= iCurr;
            iCurr ^= iMax;
            iMax ^= iCurr;
        }

        iRemainder = iMax % iCurr;

        while (iRemainder)
        {
            iMax = iCurr;
            iCurr = iRemainder;
            iRemainder = iMax % iCurr;
        }
        
        iMax = iCurr;
    }//for

    return iMax;

}

최소 공배수 는 곱 하기 나 누 기 최대 공약수 이다

int GetLCM(int *arr, int len)
{
    int multiple = 1;

    for (int i = 0; i < len; i++)
        multiple *= arr[i];

    return multiple / GetGCD(arr, len);
}