[BOJ_1929/JAVA] 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

문제

 

풀이

문제를 풀고 너무 쉽게 풀어서 정답률이 26%인게 안믿겼다..

근데 역시나 시간초과 오류가 뜨면서 다들 시간초과때문에 틀렸구나.. 라는 생각이 들었다.

그래~ 내가 남들이 못푸는걸 금방 풀 수 있을리가 없지~

해당 문제는 '에라토스테네스의 체'라는 알고리즘을 사용하여 풀었다.

 

에라토스테스스의 체란?

소수를 판별하는 알고리즘이다. 

조금 더 자세한 설명은 여기를 참고하길 바란다.

 

for문을 돌면서 제곱에 해당하는 수를 전부 true로 바꿔주어 최종적으로 false인 값만 출력하도록 하였다.

for문을 돌 때 `Math.sqrt()`하는 함수를 사용하는데, 이것은 루트값을 구해주는 함수이다.

 

코드

package Week05;

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

public class BOJ1929 {
	
	static boolean [] flag;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		String input = br.readLine();
		
		String [] nums = input.split(" ");
		
		int a = Integer.parseInt(nums[0]);
		int b = Integer.parseInt(nums[1]);
		
		flag = new boolean[b+1];
		
		get_prime();
		
		for(int i=a;i<=b;i++) {
			if(!flag[i]) {
				sb.append(i+"\n");
			}
		}
		
		System.out.println(sb);

	}
	
	static void get_prime() {
		
		//false=소수, true=소수아님.
		flag[0]=flag[1]=true;
		
		for(int i=2;i<Math.sqrt(flag.length);i++) {
			if(flag[i]) {
				continue;
			}
			for(int j=i*i;j<flag.length;j+=i) {
				flag[j]=true;
			}
		}
		
	}

}