백준 17425 약수의 합 Java [에라토스테네스의 체, 누적합]

https://www.acmicpc.net/problem/17425

17425번: 약수의 합

 

자신보다 작은 수들의 모든 약수들의 합을 구해야하므로 누적합으로 계산한다

약수 계산은 에라토스테네의 체를 사용하여 작은 수부터 시작하여 배수들을 찾아서 값을 더해준다

에라토스테네스의 체.gif

 

간단한 예시로 1부터 시작해서 일반화를 하면

배열[1]에 배열[0] 더하기, 1의 배수에 모두 1추가
배열[2]에 배열[1] 더하기, 2의 배수에 모두 2추가

...
배열[n]에 배열[n-1] 더하기, n의 배수에 모두 n추가

반복하면 예제에서 받은 입력을 인덱스로하여 배열에 접근해서 출력할 값으로 추가하면 된다

 

1부터 10까지의 과정을 숫자로 표현하면 다음과 같다

00 01 02 03 04 05 06 07 08 09 10
00 01 01 01 01 01 01 01 01 01 01
00 01 04 01 03 01 03 01 03 01 03 
00 01 04 08 03 01 06 01 03 04 03 
00 01 04 08 15 01 06 01 07 04 03 
00 01 04 08 15 21 06 01 07 04 08 
00 01 04 08 15 21 33 01 07 04 08 
00 01 04 08 15 21 33 41 07 04 08 
00 01 04 08 15 21 33 41 56 04 08 
00 01 04 08 15 21 33 41 56 69 08 
00 01 04 08 15 21 33 41 56 69 87

 

import java.io.*;

public class Main {
    static final int MAX_NUM = 1000001;
    public static void main(String[] args) throws IOException {
        long[] nums = new long[MAX_NUM];
        for (int i = 1; i < MAX_NUM; i++) {
            int n = 1;
            nums[i] += nums[i-1];
            while (i * n < MAX_NUM) {
                nums[i * n++] += i;
            }
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        for (int n = 0; n < N; n++) {
            sb.append(nums[Integer.parseInt(br.readLine())]).append("\n");
        }
        sb.setLength(sb.length() - 1);
        System.out.println(sb);
    }
}