백준 17427 약수의 합 2 Kotlin (에라토스테네스의 체)

문제 출처 : https://www.acmicpc.net/problem/17427

17427번: 약수의 합 2

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

알고리즘 분류

• 수학
• 정수론

풀이

약수의 합을 효율적으로 구하는 문제이다.

에라토스테네스의 체란 소수를 구하는 알고리즘인데, 이를 응용해서 약수의 합을 구할 수 있다.

2중 포문으로 바깥 포문에선 i를 2부터 n까지 돌리고, 안쪽 포문에선 j를 i부터 시작해서 i씩 더해나가며 n까지 돌린다.

예를들어 6이란 숫자의 약수의 합을 생각하면, 1, 2, 3, 6으로 12이다.

모든 숫자는 1이란 약수를 가지고 있으므로 1은 디폴트로 넣어주고,

i가 2일때, i가 3일 때, i가 6일 때 +2+3+6이 돼서 f[6]엔 12가 들어가게 된다.

 

이후 f[1]~f[n]까지의 합을 출력하면 끝.

여기에 누적 합까지 적용하면 아래 문제도 풀 수 있다.

2021.12.29 - [알고리즘 문제 풀이/백준] - 백준 17425 약수의 합 Kotlin (에라토스테네스의 체, 누적 합)

 

코드

val br = System.`in`.bufferedReader()

lateinit var g: LongArray
var n = 0

//에라토스테네스의 체
fun solveF(){
    for(i in 2 .. n){
        for(j in i ..n step i ){
            g[j]+=i.toLong()
        }
    }
}

//누적합
fun solveG(){
   for(i in 2 .. n) {
       g[i] += g[i-1]
   }
}


fun main() = with(System.out.bufferedWriter()) {

    n = br.readLine().toInt()
    g = LongArray(n+1){1}

    solveF()
    solveG()

    write("${g[n]}")
    close()
}