[Problem Solving/Java] 백준 1929번 - 소수 구하기

URL

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

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

첫 번째 시도

package ex1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main3 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		int a = Integer.parseInt(s[0]);
		int b = Integer.parseInt(s[1]);
		boolean[] numcheck = new boolean[b+1];
		for (int i = 0; i <= b; i++) {
			numcheck[0]=false;
		}
		for (int i=2; i*i<=b;i++) {
			if(!numcheck[i]) {
				for (int j=i*i; j<=b; j+=i) {
					numcheck[j]=true;
				}
			}
		}
		for (int i=a; i<=b; i++) {
			if(!numcheck[i]&&i!=1&&i!=0) {
				System.out.println(i);
			}
		}
	}
}

해결 방법

• 처음에는 % 연산을 통해 나머지가 0이고 나누는 수가 자기 자신과 같으면 ArrayList에 그 수를 저장했다. 그리고 마지막에 그 리스트를 반환했다. 그렇게 했더니 시간초과가 나왔다. 알고리즘을 에라토스테네스의 체로 다시 코드를 수정했다. for문을 통해 i를 반복하는데, ArrayList를 모두 false로 초기화 하고 i가 false라면 소수이다. 그리고 i가 false일 때 인덱스가 i의 배수인 ArrayList 를 Remove 와 add를 사용해서 Array를 모두 true로 바꾼다. 이렇게 해도 시간초과가 나와서 ArrayList 대신 Array를 사용했다. Remove와 add 대신 바로 true나 false를 대입했다. 그리고 1 200을 입력하면 1도 포함돼서 나오는 경우나 1 13을 입력하면 13이 빼고 나오는 경우를 for문의 <, <=를 수정하여 제출했다.

어려웠던 점 / 고쳐야할 점

• 에라토스테네스의 체를 구현하는게 어려웠다.