코드업(codeup) 2055 : 두 수의 약수 구하기 C언어

▶문제 : 두 수의 약수 구하기 (codeup.kr)

두 수의 약수 구하기

 

▶코드 작성

#include <stdio.h>

int arr[100000];

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);

    int len = 0;//배열 길이
    for (int i = 1; i * i <= b; i++)
    {//i값과 b/i값을 같이 구하기 때문에 i*i<=b 조건으로 최소한의 반복을 하게 함
        if (b % i == 0)//i로 나누어 떨어질 때
        {
            arr[len++] = i;//i는 약수
            arr[len++] = b / i;//b를 i로 나눈 수도 약수
        }

        if (i * i <= a && a % i == 0)//a또한 같은 조건으로( a<=b )
        {
            arr[len++] = i;
            arr[len++] = a / i;
        }
    }

    int min, temp;
    for (int i = 0; i < len - 1; i++)//선택 정렬 오름차순
    {
        min = i;
        for (int j = i + 1; j < len; j++)
        {
            if (arr[min] > arr[j]) min = j;
        }
        if (i != min)
        {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }

    int num = 0;//중복 방지 변수
    for (int i = 0; i < len; i++)
    {
        if (arr[i] != num)//중복되지 않을 때
        {
            printf("%d ", arr[i]);
            num = arr[i];
        }
    }

    return 0;
}

 

▶해석

반복문으로 a와 b의 약수들을 a% i==0와 b% i==0로 찾아준다. 약수 배열에 i값과 a/i, b/i값을 넣어준다. 이때 반복문 조건은 i*i <=b이다.

 예를 들어 a가 16이면 1,2,4,8,16이 약수이다. 여기서 i값이 1,2,4까지만 가도 나머지 약수를 a/i로 찾을 수 있다. i가 4를 넘으면 a/i값은 작아진다. 그럼 i값과 a/i값만 바뀐 채로 다시 약수를 찾는 셈이 되는 것이다. 그러므로 16은 4*4가 마지막으로 찾는 수가 된다. 그런 느낌으로 다른 수 또한 적용된다.

 다른 약수를 모두 구한 후 선택 정렬로 정렬한 다음 변수 num에 출력한 수를 저장하면서 중복하지 않도록 출력해주었다.