[C++] 모두의 약수

[목적]

자연수 N을 입력하면 1부터 N까지의 숫자들의 약수의 개수를 출력한다.

 

[입력 예제]

8

 

[출력 예제]

1 2 2 3 2 4 2 4

 

8을 입력하면 1부터 8까지의 숫자들의 약수의 개수를 출력한다.

이때 제한시간은 1초안에 출력 될 수 있도록 한다.

---

[코드 1]

#include <iostream>

using namespace std;

int main(void) {
    
    int num, cnt = 0;
	
    cin >> num;
	
    for(int i=1; i<=num; i++){
        cnt = 0;
        for(int j=1; j<=i; j++){
            if(i%j == 0)
                cnt++;
        }
        cout << cnt << " ";
    }
    
    return 0;
}

 

[실행 결과 1]

마지막 경우에서 시간초과가 나왔다. 항상 1부터 끝까지 돌아야 하기에 시간 복잡도가 거의 N^2에 가까워서 그렇다고 한다.

---

[코드 2]

#include <iostream>

using namespace std;

int main(void) {
    
    int num;
    int cnt[50001] = {0};
	
    cin >> num;

    for(int i=1; i<=num; i++){
        // j가 i부터 시작해서 i의 배수들만 개수를 1씩 늘려준다.
        for(int j=i; j<=num; j=j+i){
            cnt[j]++;
        }
    }
    
    for(int i=1; i<= num; i++){
        cout << cnt[i] << " ";
    }
    return 0;
}

1. 1부터 N까지의 수의 N을 입력받는다.

2. 1부터 N까지 반복하며 반복문 안에서 i부터 N까지 반복한다.

3. 이중 for문 안의 for문에서 i의 배수들만 cnt[j] 배열안의 숫자를 1씩 늘려준다.

4. cnt배열을 출력한다.

 

[실행 결과 2]