[JAVA] 백준 1929번 : 소수 구하기

 

---

 

• 생각

N부터 M까지의 수 중 소수를 찾는 문제이다.

 

1. 에라토스테네스의 체를 통해 빠르게 소수를 찾는 방법이 있다. (잘 모르면 링크를 타고 들어가서 이해하길..)

 

2. 위의 방법으로 소수를 찾은 후 N부터 M까지 수 중에서 소수만 출력하면된다.

 

• 코드

정답 코드 : 에라토스테네스의 체를 통해 N과 M사이의 소수를 찾은 뒤 출력해줌

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static boolean[] check;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		FindDecimal();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		sb = new StringBuilder();
		check = new boolean[M + 1];
		check[0] = check[1] = true;

	}

	private static void FindDecimal() {
		for (int i = 2; i <= M; i++) {
			if (check[i] == true) {
				continue;
			}
			// 해당 수로 나누어 떨어지는 수는 소수이므로 true로 check
			for (int j = i + i; j <= M; j+=i) {
				check[j] = true;
			}
		}
		for (int i = N; i <= M; i++) {
			if (check[i] == false)
				sb.append(i + "\n");
		}

	}
}