BOJ - 소수 구하기

1929 소수 구하기 : https://www.acmicpc.net/problem/1929

---

Problem

---

Solve

에라토스테네스의 체를 이용한 문제입니다.

에라토스테네스의 체는 2부터 M까지의 수 중 소수를 찾아낼수 있는 방법입니다.
어떠한 수가 주어졌을때, 해당 수가 소수라면, 자신의 제곱부터 M까지 자신의 배수는 소수가 아니게 됩니다.
즉, 소수인 값의 배수를 지우게 되면 소수인 값만 남게 되는것입니다.

이때, 에라토스테네스의 체의 특징은 2부터 M까지의 값중 소수를 찾을때, 2부터 M의 루트 까지의 배수값만 구해줘도 소수를 판별할수 있다는 것입니다.

for(int i=2;i<=Math.sqrt(M);i++)

---

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		boolean[] check = new boolean[M+1];
		check[0] = check[1] = true;

		for(int i=2;i<=Math.sqrt(M);i++){
			if(check[i]) continue;
			for(int j=i*i;j<=M;j+=i){
				check[j] = true;
			}
		}

		StringBuilder sb = new StringBuilder();
		for(int i=N;i<=M;i++){
			if(!check[i]) sb.append(i).append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference

https://firework-ham.tistory.com/8