백준 17425 약수의 합 Kotlin (에라토스테네스의 체, 누적 합)

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

17425번: 약수의 합

문제

두 자연수 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)을 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

알고리즘 분류

• 수학
• 정수론
• 누적 합
• 소수 판정
• 에라토스테네스의 체

풀이

에라토스테네스의 체 + 누적 합 문제이다.

에라토스테네스의 체란 1~N의 수가 소수인 지 판별하는 알고리즘이다.

1부터 어떠한 수의 배수들은 모두 소수가 아니다. 라는 개념으로 접근하는데, 이를 이용해 해당 수의 약수들의 합을 구할 수 있다.

위의 에라토스테네스의 체 응용으로 1부터 N까지의 수 i에 대한 약수들의 합 f(i)를 구한다.

이후 이 f(i)들로 누적 합 g(i)를 만들고, 각 테스트케이스마다 g(i)를 출력한다.

 

누적 합을 이용하면 T번 만큼 반복해야 하는 f(1)+..+f(i)의 과정을 한 번만 하면 된다.   

 

코드

val MAX = 1000001
val br = System.`in`.bufferedReader()
//1<=n<=1000000
val g = LongArray(MAX){1}

fun solveF(){
    for(i in 2 until MAX){
        for(j in i until MAX step i){
            g[j]+=i.toLong()
        }
    }
}

fun solveG(){
    for(i in 2 until MAX){
        g[i] += g[i-1]
    }
}

fun main() = with(System.out.bufferedWriter()){
    val t = br.readLine().toInt()
    solveF()
    solveG()
    repeat(t){
        write("${g[br.readLine().toInt()]}\n")
    }
    close()
}