백준 1929번 소수 구하기 #에라토스테네스의 체

소수 구하기 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

256 MB

109641

31049

21983

27.222%

문제

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

입력

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

출력

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

예제 입력 1 복사

3 16

예제 출력 1 복사

3 5 7 11 13

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
val br = BufferedReader(InputStreamReader(System.`in`))
fun main()=with(br){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val (m,n) = readLine()!!.split(" ").map{it.toInt()}
    // 사이즈가 n+1인 이유는 입력받은 값을 m,n에 저장하는데
    // 배열에 index가 n까지가 될수있도록 n+1까지 생성합니다.
    // -1로 초기화 한 이유는 에라토스테네스의 체의 개념을 사용하기때문에
    // 0이 된 값과 구분해 주기 위함입니다.
    var list = MutableList(n+1,{-1})
    var key = 0
    for(i in m .. n){
        list[i]=i
    }
    // 에라토스테네스의 체 개념
    // 2부터 시작해서 시작하는 수의 제곱이 되는 수는 배열의 값을 0으로 바꾼다.
    // 시작 수는 왜 0으로 안 만드냐면 2같은경우 소수인데 생략이 될 수도 있기
    // 때문이다.
    for(i in 2..n){
        if(list[i]==0)
            continue
        for(j in i+i .. n step i) {
            list[j] = 0
        }
    }
    for(i in m .. n){
        // 1은 소수가 아니므로 생략합니다.
        if(i==1)
            continue
        if(list[i]!=0) {
            bw.write("${list[i]}\n")
        }
    }
    bw.flush()
    bw.close()
}