[알고리즘 연습] N까지의 약수 갯수 모두 구하기 (by C++)

N까지의 약수 갯수 모두 구하기

• N을 입력받고 1~N까지의 약수를 하나씩 출력한다.
• 예를 들어, 8을 입력하면 1의 약수 개수 ~ 8의 약수 개수를 하나씩 출력하여, 1 2 2 3 2 4 2 4 와 같이 출력된다.

---

풀이 (단순 접근)

#include <stdio.h>

int main() {
    //freopen("input.txt", "rt", stdin);
    int n, i, j, num = 0;
    scanf("%d", &n);

    for(i=1; i<=n; i++) {
        for(j=1; j<=i; j++) {
            if(i % j == 0) {
                num++;
            }
        }
        printf("%d ", num);
        num = 0;
    }

    return 0;
}

- 이와 같이 단순한 방법도 있지만, 효율이 그리 좋지 못하다. (O(N^2)의 시간복잡도를 갖기 때문이다.)

---

풀이 (효율적)

#include <stdio.h>

int cnt[50001];

int main() {
    //freopen("input.txt", "rt", stdin);    
    int n, i, j;
    scanf("%d", &n);
    for (i=1; i<=n; i++) {
        for (j=i; j<=n; j=j+i){    
            cnt[j]++;        
        }
    }

    for(i=1; i<=n; i++) {
        printf("%d ", cnt[i]);
    }

    return 0;
}

- 역으로 생각하여, N까지의 각 숫자의 배수를 각 숫자의 약수로 더해주었다.

- 마찬가지로 O(N^2)이라고 볼 수도 있지만, 또 하나의 for문을 잘 살펴보면 그 과정이 매우 간단해졌음을 알 수 있다.

- O(N*logN)에 가까운 효율을 보여준다. (같은건아님)