백준 [17427] 약수의 합 2 (자바)

문제

풀이

배수의 성질을 이용한 약수를 구하는 방법을 사용한다.

알고리즘 풀이에서 배수를 이용하여 약수를 구하는 방식이 선호된다.

 

6을 까지 약수들을 보면

1 -> 1

2 -> 1 2

3 -> 1 3

4 -> 1 2 4

5 -> 1 5

6 -> 1 2 3 6

 

6이하 자연수 중 1을 약수로 가지는 수의 개수 = 6개 = 6 / 1

6이하 자연수 중 2을 약수로 가지는 수의 개수 = 3개 = 6 / 2

6이하 자연수 중 3을 약수로 가지는 수의 개수 = 2개 = 6 / 3

6이하 자연수 중 4을 약수로 가지는 수의 개수 = 1개 = ...

6이하 자연수 중 5을 약수로 가지는 수의 개수 = 1개 = N / M

6이하 자연수 중 6을 약수로 가지는 수의 개수 = 1개

 

약수의 합은 1 ~ N 까지 모든 (M * N / M)의 합을 구해주면 된다.

 

정답코드

package com.baekjoon.p17427;

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        long sum = 0;

        for (int i = 1; i <= N; i++) {
            sum += (long) (i * (N / i));
        }

        System.out.println(sum);
        sc.close();
    }
}