[백준] 1929 소수 구하기

문제 출처: www.acmicpc.net/problem/1929

1929번: 소수 구하기

: 입력으로 M과 N이 주어지고 M이상 N이하인 소수를 모두 출력해야 한다.

: 이때, 소수를 구하는 방법을 모든 수를 순회하면 시간 초과가 나는 것 같다.

: 따라서 에라토스테네스의 체 라는 알고리즘을 사용할 수 있는데 각 수를 순회하며 그 수의 배수들을 지워나가며 마지막까지 남은 수들이 소수가 되는 방식이다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
	
		boolean[] v = new boolean[M+1];
		ArrayList<Integer> primes = new ArrayList<>();
		for(int i = 2; i <= M; i++) {
			if(!v[i]) {
				primes.add(i);
				for(int j = i+i; j <= M; j+=i) {
					v[j] = true;
				}
			}
		}
		for(int i : primes) {
			if(i >= N && i <= M)sb.append(i + "\n");
		}
		System.out.println(sb);
	}
}

www.acmicpc.net/problem/1929