[JAVA 알고리즘]BAEKJOON 1929번 소수 구하기

소수 구하기

---

문제 설명

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

제한사항

• 없음

입력

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

출력

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

입출력 예

answers	return
3 16	3 5 7 11 13

---

나의 문제풀이

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String array[] = br.readLine().split(" ");
		int M = Integer.parseInt(array[0]);
		int N = Integer.parseInt(array[1]);
		
		for (int i = M; i <= N; i++) {
			int cnt = 0;
			
			for (int j = 2; j*j <= i; j++) {
				if (i % j == 0) { 
					cnt++;
					break;
				}
			}
			if (cnt == 0 && i != 1) System.out.println(i);						
		}
	}
}

• 공백으로 구분된 입력값을 버퍼리더를 이용하여 받아 split함수를 이용해 배열에 넣어준다.
• 에라토스테네스의 체 방식으로 M에서 N까지의 소수를 찾아준다.

---

느낀 점

다른 문제에서 했던 방식으로 동일하게 풀 수 있어서 기존 방식으로 풀어보고 다른 방식으로 찾아서 풀어보았다.

배열을 이용하여 에라토스테네스의 체를 구성하여 출력하니 속도가 조금 더 빨라졌다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String array[] = br.readLine().split(" ");
		int M = Integer.parseInt(array[0]);
		int N = Integer.parseInt(array[1]);
		boolean range[] = new boolean[N+1];
		
		range[1] = true;
		
		for (int i = 2; i <= N; i++) {
			if (range[i]) continue;
			for (int j = i + i; j <= N; j += i) { // i를 제외한 배수들은 소수가 아니다.
				range[j] = true;
			}
		}
		
		for (int i = M; i <= N; i++) {
			if (!range[i]) System.out.println(i);
		}
	}
}