[백준/BOJ] 1929번 : 소수 구하기 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

1929번: 소수 구하기

---

- 문제 -

 

난이도 실버 3 문제이다.

 

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

에라토스테네스의 체로 푼다.

우선 에라토스테네스에 체에대해 알고 있으면 매우 쉽게 푸는 문제이기 때문에 모른다면 먼저 그것부터 공부하고 풀어야한다.

필자가 간략하게 설명은 하겠지만 이해가 안된다면 구글링을 하도록.

에라토스테네스의 체 방식은 2부터 소수의 제곱과 그 이후 배수들을 제외해 나가는 방식이다.

1~10을 보자. 1은 소수가 아니니 제외. 2~10이다.

2는 소수이다, 그럼 2의 제곱부터 배수들을 지운다. 4, 6, 8, 10이다.

다음 수 3은 소수이다. 그럼 3의 제곱부터 배수들을 지운다. 9.

여기까지만 하는데 내가 구할 수는 10까지 이고, 제곱해서 10이 넘지 않는 수까지만 해주면 된다.

10은 3의 제곱보다 크고, 5의 제곱보다 작다. 그러니 3까지만 해준다.

그럼 제외한 수는 4, 6, 8, 9, 10이다. 그럼 나머지는 소수이니 소수는 2, 3, 5, 7이 되는 것이다. 이것이 에라토스테네스의 체 방법이다.

하나만 더 예를 들면 25이다. 소수 5의 제곱과 같으니 소수 5까지만 진행한다.

2의 배수, 3의 배수, 5의 배수를 제외한다. 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24 / 9, 12, 15, 18, 21, 24 / 25 수들을 제외한 나머지가 소수인 것이다.

그럼 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23이 되는 것이다.

 

입력값 M과 N M~ N 중 소수를 구하는 것이다.

1~ N까지 에라토스테네스의 체를 적용시키고. M~N의 값을 출력한다.

 

출력은 StringBuilder에 저장해서 한번에 출력한다. 그냥 출력해도 맞긴하겠지만 100만까지의 값이 들어갈 수 있기에 StringBuilder를 사용하는 것을 권장한다.

---

-풀이-

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		//소수 판별 배열 N까지 나타내기위해 범위는 N+1로
		//소수 판별은 꼭 boolean 형을 사용하지 않고 int형이나 String형 같이 다른 자료형을 사용해도 된다.
		boolean[] arr = new boolean[N + 1];
		StringBuilder sb = new StringBuilder();
		
		//0과 1은 소수가 아니다.
		arr[0] = true;
		arr[1] = true;
		
		//문제에서 말한 제곱해서 N을 넘지 않을때까지만 소수의 배수를 제외해 주면 된다.
		for(int i = 2; i * i <= N; i++) {
			//소수일때
			if(!arr[i]) {
				//j에는 소수의 배수들이 들어와야하기때문에 아래 조건이 들어간다.
				for(int j = i * i; j <= N; j += i) {
					//소수의 배수들에는 true를 저장
					arr[j] = true;
				}
			}
		}
		
		for(int i = M; i <= N; i++) {
			if(!arr[i]) sb.append(i).append("\n");
		}
		System.out.println(sb);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.