[A&I Code Camp] Day22

✍   Kotlin을 PS 문제 풀기

소속중인 A&I 동아리에서 코딩역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 kotlin을 기반으로 작성합니다.

소수 판별 알고리즘

이번 주 주제는 소수 판별 알고리즘이며
백준에 하루 한 문제를 풀어가며 작성할 것입니다.
소수 판별 알고리즘
해당 내용은 위 포스트에 작성하였습니다.

4134번

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

이 문제는 내가 입력한 수를 받고
수만큼 미지수를 넣었을 때 똑같거나 가장 가까운 소수를 구하는 문제입니다.

Solve

1. 내가 입력한 미지수 만큼 소수를 체크(prime)할 수 있는 함수를 만들어 준 뒤
2. 원하는 수 만큼 repeat문을 통해 숫자를 계속 받아주고
3. 그 수가 2이하라면 소수가 2가 가장 가깝기에 2를 출력해주고
4. 수를 check 함수에 넣어 반복문을 돌려주는데 소수가 발견될 때까지
   계속 num에 1을 더해가며 제곱근 만큼 수가 돌다가
5. true를 반환하는 시점에는 약수가 자기자신 밖에 없는 것이며
   가장 가까운 소수가 존재하기에 그것을 반환해 주었다.

import kotlin.math.sqrt

fun main() {
    fun check(n: Long): Boolean {
        val sqrt = sqrt(n.toDouble()).toLong() + 1
        for (i in 2..sqrt) {
            if (n % i == 0L) return false
        }
        return true
    }


    repeat(readln().toInt()){
        var num = readln().toLong()
        while (true) {
            if(num <= 2){
                println(2)
                break
            }
            else if (check(num)) {
                println(num)
                break
            } else {
                num++
            }
        }
    }
}

📌 결론

해당 문제는 범위가 넓어 에라토스테네스 체의 알고리즘을 사용하려다
컴파일 에러가 발생할 수 있으니 구분하여 사용하자.