[BOJ] 1929. 소수 구하기

BaekJoon 1929. 소수 구하기

* 문제의 저작권은 BOJ 및 문제를 만든 사람에게 있습니다.

 

 

 

 

 

[문제 접근]

범위가 100만까지기 때문에 전에 풀었던 소수 찾기처럼 풀면 시간 초과가 날 수 있기 때문에 에라토스테네스의 체로 풀어야 한다.

에라토스테네스의 체는 2를 빼고 2의 배수를 제외하고, 3을 빼고 3의 배수를 제외하는 방식으로 마지막까지 남는 수가 소수다.

 

 

 

 

 

 

 

 

 

 

[코드]

import java.util.Scanner;

public class Main_1929 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int M = sc.nextInt();
		int N = sc.nextInt();
		boolean[] prime= new boolean[N+1];
		
		prime[1] = true;
		
		for (int i = 2; i <= N; i++) {
			for (int j = 2; i*j <= N; j++) {
				prime[i*j] = true;
			}
			
		}
		
		for (int i = M; i < prime.length; i++) {
			if (!prime[i]) {
				System.out.println(i);
			}
		}

	}
}