C++로 숫자의 약수를 구하고 출력하는 프로그램 작성법

약수(인수)란 서로 곱했을 때 어떤 수가 되는 숫자들을 말합니다.

예를 들어, 5 × 3 = 15이므로 5와 3은 15의 약수입니다. 마찬가지로 15 × 1 = 15이므로 1과 15 역시 15의 약수입니다.

아래는 하나의 숫자에 대한 모든 약수를 화면에 출력하는 C++ 프로그램입니다.

예제 1: 기본 구현

#include<iostream>
using namespace std;
int main() {
    int num = 20, i;
    cout << "The factors of " << num << " are : ";
    for(i=1; i <= num; i++) {
        if (num % i == 0)
             cout << i << " ";
    }
    return 0;
}

출력 결과

The factors of 20 are : 1 2 4 5 10 20

위 프로그램에서 for 루프는 1부터 num까지 차례대로 반복하며, 각 반복마다 num % i(나머지 연산)의 결과가 0인지 확인합니다. 나머지가 0이라는 것은 num이 i로 나누어떨어진다는 의미이므로, i는 num의 약수가 되어 화면에 출력됩니다.

for(i=1; i <= num; i++) {
    if (num % i == 0)
        cout << i << " ";
}

예제 2: 함수를 사용한 구현

위 프로그램은 약수를 계산하는 로직을 별도의 함수로 분리하여 작성할 수도 있습니다. 이렇게 하면 코드의 재사용성과 가독성이 한층 향상됩니다.

#include<iostream>
using namespace std;
void factors(int num) {
    int i;
    for(i=1; i <= num; i++) {
        if (num % i == 0)
             cout << i << " ";
    }
}
int main() {
    int num = 25;
    cout << "The factors of " << num << " are : ";
    factors(num);
    return 0;
}

출력 결과

The factors of 25 are : 1 5 25

위 프로그램에서 factors() 함수는 매개변수로 전달받은 num의 모든 약수를 찾아 출력하는 역할을 담당합니다. 이 함수는 main() 함수 내에서 다음과 같이 호출됩니다.

factors(num);

factors() 함수 내부의 for 루프 역시 1부터 num까지 반복하며, 나머지가 0인 값을 num의 약수로 판별하여 출력합니다.

성능 최적화 팁

위 알고리즘은 1부터 num까지 모든 수를 검사하므로 시간 복잡도가 O(n)입니다. num이 매우 큰 값이라면, 1부터 √num까지만 검사한 뒤 발견된 약수의 짝이 되는 값(num / i)을 함께 처리하는 방식으로 시간 복잡도를 O(√n)까지 단축할 수 있습니다.