1929_소수 구하기 (JAVA)

1929번: 소수 구하기

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();

		boolean[] check = new boolean[N+1];
		for(int i=2; i<=N; i++){ //2의배수부터 체크해야되니까 2부터 N까지 true로
			check[i] = true;
		}

		for(int i=2; i<=N; i++){
			if(!check[i]) //이미 체크한거는 다시 체크X
				continue;
			for(int j=i+i; j<=N; j+=i){
				check[j] = false; //j를 제외한 j의 배수 체크하기
			}
		}

		for(int i=M; i<=N; i++){
			if(check[i])
				System.out.println(i);
		}
	}
}

 

이전에 소수구하는 문제를 모든수를 체크하는 방식으로 ㅎㅎ.. 효율성을 하나도 고려안한채 풀었는데

이 문제에서는 시간초과가 난다. 정신차리고 에라토스테네스의체 이용해서 풀었다ㅎ_ㅎ

 

소수

 

 

[문제 풀이 생각 과정]

 

1. M~N 의 수만 체크하면 되지만, 에라토스테네스의체를 이용하려면 2의배수부터 체크해야한다.

    그러므로 check[]배열은 2부터 N까지 true로 초기화해준다.

 

2. 2~N까지의 모든 수에 대하여

    2를 제외한 2의배수, ... N을 제외한 N의배수까지 각 배수를 false로 체크한다.

 

3. true인 수 == 소수!

    왜냐면 n의 배수로 체크가 되지 않았다는건, 1과 자기자신만을 약수로 갖는다는 의미이기 때문