[백준] 1929번 소수구하기

소수구하기 문제다.

 

이 문제는 에라토스테네스의 체를 사용해야 하는 문제다.

 

우선 isNotPrime이라는 배열을 선언해준다. 이때 이 배열은 boolean타입이다.

boolean 타입은 기본적으로 false로 초기화 되어있다. 

 

isNotPrime[0] = isNotPrime[1] = true;
		
		for(int i = 2; i * i <= M; i++) {
			if(!isNotPrime[i]) {
				for(int j = i * i; j <= M; j += i) {
					isNotPrime[j] = true;	
				}
			}
		}

 

이 코드가 핵심이다. 0, 1은 소수가 아니다.

그렇기 때문에 배열은 true가 된다.

 

2부터 for문을 돌렸을 때 i값의 제곱수에 준하거나 그보다 작은 수까지 판별하게 되는데

이게 에라토스테네스의 체이다.

// 2부터 n의 제곱근까지의 모든 수를 확인

 

그리고 그 이하의 수는 모두 판별했기 때문에 i * i 부터 보게 된다.

1) 자기 자신은 소수

2) 자기의 배수는 모두 소수가 아님

 

이렇게 모두 true를 넣어주고 원래 초기값인 false은 가만히 있게된다.

그렇게 소수인 배열만 잘 출력을 해주면 결과값이 나온다.

 

package com.study;

import java.io.*;
import java.util.*;

public class Main {
	static final int LIMIT = 1000000;
	static final boolean[] isNotPrime = new boolean[LIMIT + 1]; // 기본적으로 다들 소수가 아닌~
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		isNotPrime[0] = isNotPrime[1] = true;
		
		for(int i = 2; i * i <= M; i++) {
			if(!isNotPrime[i]) {
				for(int j = i * i; j <= M; j += i) {
					isNotPrime[j] = true;	
				}
			}
		}
		
		for(int i = N; i <= M; i++) {
			if(!isNotPrime[i]) {
				System.out.println(i);
			}
		}
		
	}

}