Kotlin 🍬 백준 15단계 :: 1929 번

소수 구하기

문제   |

  M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력   |

  첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력   |

  한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

풀이  |

  에라토스테네스의 체 알고리즘을 이용해 소수 도출 (외워두기)

 

 

답안  |

1. 에라토스테네스의 체 알고리즘 사용

fun main() {
    val (M, N) = readLine()!!.split(" ").map { it.toInt() }
    
    val primes = sieveOfEratosthenes(N)
    
    for (i in M..N) {
        if (primes[i]) {
            println(i)
        }
    }
}

fun sieveOfEratosthenes(limit: Int): MutableList<Boolean> {
    val sieve = MutableList(limit + 1) { true }
    sieve[0] = false
    sieve[1] = false

    var p = 2
    while (p * p <= limit) {
        if (sieve[p]) {
            var i = p * p
            while (i <= limit) {
                sieve[i] = false
                i += p
            }
        }
        p++
    }
    return sieve
}

 

2. for문 이용한 소수찾기

fun main() {
    val (M, N) = readLine()!!.split(" ").map { it.toInt() }
    
    for (i in M..N) {
        if (isPrime(i)) {
            println(i)
        }
    }
}

fun isPrime(num: Int): Boolean {
    if (num == 1) {
        return false
    } else if (num == 2) {
        return true
    } else {
        for (i in 2..(Math.sqrt(num.toDouble())).toInt()) {
            if (num % i == 0) {
                return false
            }
        }
        return true
    }
}