백준 - 1929번 - 소수 구하기

1929번

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

public class Main {
	static boolean[] prime;

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st  = new StringTokenizer(bf.readLine());
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());

		makePrime(B);
		for (int i = A; i<prime.length; i++) {
			if (prime[i] == false) {
				System.out.println(i);
			}
		}
	}

	static boolean[] makePrime(int B) {

		prime = new boolean[B+1];

		prime[0] = true;
		prime[1] = true;

		for (int i = 2; i<=Math.sqrt(B); i++) {
			if (prime[i]) {
				continue;
			}

			for (int j = i * i; j<B+1; j=j+i) {
				prime[j] = true;
			}
		}
		return prime;
	}
}

풀이

---

입력받은 두 숫자 사이에 소수들을 찾아서 출력하는 문제다.

입력받은 수중 큰 수 내부의 소수들을 찾는 메서드를 에라토스테네스의 체를 활용해서 구한다.

출력할때 입력받은 수중 작은 수부터 인덱스를 적용하고 false인것만 출력하면 된다.