[백준] 1929 (소수 구하기)

#1 알고리즘

인덱스가 0 ~ 1000000 (문제에서 주어진 최댓값)인 Boolean형 배열 isPrimes을 선언한다. 이 배열은 이 배열의 어떤 index가 소수인지 아닌지를 true or false로 저장하기 위한 배열이다. 우선 isPrimes의 모든 index의 값을 true로 초기화한다.

 

isPrimes[0]은 사용하지 않으며, isPrimes[1]에는 false를 대입한다.

 

이제 isPrimes[2]부터 시작해 오름차순으로 배열을 순회한다. isPrimes[x]이 true면 해당 x을 저장한다. 그리고 isPrimes[x * 2], isPrimes[x * 3], isPrimes[x * 4], ...에는 false를 대입한다. x++을 하고 다시, isPrimes[x]이 true면 해당 x을 저장한다. 그리고 isPrimes[x * 2], isPrimes[x * 3], isPrimes[x * 4], ...에는 false를 대입한다. x++을 하고 다시, ... (반복)

 

m보다 같거나 크고 n보다 같거나 작은, 저장된 x값을 출력한다.

 

#2 코드 - 코틀린

import java.io.BufferedWriter
import java.io.OutputStreamWriter

val scopeMax = 1000000
val isPrimes: Array<Boolean> = Array(scopeMax + 1) {true}
var m = -1
var n = -1

fun main() {
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    
    val mAndN = readln().split(" ")
    m = mAndN[0].toInt()
    n = mAndN[1].toInt()

    isPrimes[1] = false
    for(i: Int in 2..(n/2)) { // (n/2 + 1) ~ (n)은 쓸데없는 순회다
        if(isPrimes[i] == true) {
            markNonPrimes(i)
        } else { // isPrimes[i] == false
            continue
        }
    }
    
    for(i: Int in m..n) {
        if(isPrimes[i] == true) {
            bw.write("${i}\n")
        }
    }
    
    bw.flush()
    bw.close()
}

fun markNonPrimes(primeNumber: Int) {
    for(i: Int in 2..(n/primeNumber)) {
        isPrimes[primeNumber * i] = false
    }
}