개요

💡 C++로 약수를 구해보자.

C++로 정수 N의 약수를 구해보자.

참고 자료

본론

---

정수 N의 약수 구하기

1~N까지 구하기

가장 간단하고 원초적인 방법입니다.

1~N까지 나눠보고 0으로 나누어 떨어지면 약수임을 판별합니다.

int main()
{
	int N = 15;
    int count = 0;
    
    for (int  i = 1;i<=N;i++)
    {
    	if (N%i == 0)
        {
        	count++;
        }
    }
    
	return 0;
}

위 방법의 시간복잡도는 O(n)으로 n이 클수록 비효율적이게 됩니다.
이를 개선해보겠습니다.

1 ~ N/2까지 구하기

핵심 아이디어는 약수는 대칭적으로 존재한다는 것입니다.

N/2 이상의 수는 n의 약수가 될 수 없으므로, 약수를 찾기 위해 최대 n/2까지만 반복해도 됩니다.

int main()
{
    int N = 15;
    int count = 0;

    for (int i = 1; i <= N / 2; i++) {
        if (N % i == 0) {
            count++;
        }
    }

    count++; // N 자체도 약수이므로 1 추가

    return 0;
}

하지만 이 역시도 O(n/2)의 시간복잡도로 단순히 O(n)과 별반 다를게 없습니다.

이를 좀 더 개선해보겠습니다.

1 ~ √n까지 구하기

i가 N의 약수라면, N/i도 약수입니다. 이때 i == N / i인 경우에는 중복을 방지하기 위해 count를 한 번만 증가시킵니다.

그렇지 않은 경우에는 i와 N/i 두 약수를 각각 하나씩 카운트하기 때문에 count를 2만큼 증가시킵니다.

int main()
{
    int N = 15;
    int count = 0;

    for (int i = 1; i <= std::sqrt(N); i++) {
        if (N % i == 0) {
            if (i == N / i) {
                count++; // i와 N/i가 같으면 한 번만 증가
            } else {
                count += 2; // i와 N/i가 다르면 두 번 증가
            }
        }
    }
    
    return 0;
}

이 경우의 시간복잡도는 O(√n)으로 엄청나게 개선됨을 볼 수 있습니다.

만약 N이 1억이라고 할 때,
첫번째 방법은 하나의 N에 대해서 1억번의 연산을,
두번째 방법은 하나의 N에 대해서 5천만번의 연산을,
세번째 방법은 하나의 N에 대해서 1만번의 연산만으로 구할 수 있습니다.

---

마무리

N/2까지 구하는 경우 N이 짝수이거나, 특정 약수를 조기에 발견하는 일부에 한해 최적화가 되는 경우가 있으나,

이는 매우 제한적이니 가능하면 1~√n의 범위에서 구하는 것이 가장 효율적입니다.