백준 1929번
https://www.acmicpc.net/problem/1929

문제

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

---

생각하기

에라토스테네스의 체를 사용하면 쉽게 풀 수 있는 문제이다.

에라토스테네스는 원하는 숫자의 소수를 찾을 때,
해당 값의 루트를 씌운 값의 배수까지 소수인지를 찾으면 되는 방식이다.

하나씩 모두 대입해서 소수를 구하면 너무 비효율적이기도 하고, 이 문제를 풀 수 없기때문에 꼭 알아야하는 알고리즘이다.

동작

    for(i in 2.. Math.sqrt(N+1.toDouble()).toInt()) {
        if(arr[i] == true) {
            continue;
        }

        for(j in i*i..N step +i) {
            arr[j] = true;
        }
    }

    for(i in M..N) {
        if(arr[i] == false) {
            sb.append(i).append('\n')

Math.sqrt를 통해서 N까지의 값에서 루트를 씌운 값을 알 수 있다.

16까지의 소수를 찾는다면, 16의 루트 값인 4까지만 반복해서
2의 배수, 3의 배수, 4의 배수까지만 찾는다면

마지막에 남는 수는 소수가 된다.

---

코드

import java.util.*;
import java.io.*;

fun main() {
    var br = BufferedReader( InputStreamReader(System.`in`))
    var st = StringTokenizer(br.readLine())
    var sb = StringBuilder();

    var M = st.nextToken().toInt()
    var N = st.nextToken().toInt()
    var arr = Array(N+1, {false})
    arr[0] = true; arr[1] = true;

    for(i in 2.. Math.sqrt(N+1.toDouble()).toInt()) {
        if(arr[i] == true) {
            continue;
        }

        for(j in i*i..N step +i) {
            arr[j] = true;
        }
    }

    for(i in M..N) {
        if(arr[i] == false) {
            sb.append(i).append('\n')
        }
    }

    print(sb)
} // End of main