1. Problem 📃

[ 소수 구하기 ]

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

[ 문제 ]

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

2. Input 📇

[ 입력 ]

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

3. Output 📠

[ 출력 ]

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

4. Example 📚

[ 입출력 예시 ]

예제 입력	예제 출력
3 6	3 5 7 11 13

5. Solution 🔑

1. 우선 소수인 값들을 담아줄 StringBuilder(sb)를 하나 선언해주었다.
   두 변수(M, N)을 선언하고 두 값을 받아 M부터 N까지의 수들 중 소수인 수를 확인해줄 것이다.
   
   
2. 소수 판별을 위한 메서드(get_prime)를 하나 작성해준다.
   (소수 판별을 위한 방법은 총 3가지가 존재하는데 [ 7. Growth 🍄 ]에 정리해두겠다.)
   
   
   메서드에는 2부터 입력 받은 값(val)의 제곱근(Math.sqrt(val))까지 수들이 입력 받은 값과 나누어 떨어지는지 확인하는 방법을 사용한다.
   
   
3. 2보다 작은 수는 소수가 아니므로 소수를 판별할 필요가 없으므로 메서드를 종료시킨다.
   2가 들어오면 StringBuilder(sb)에 입력 값(val)을 append하고 개행시킨다.
   그 이상의 숫자들이 들어오면 2부터 val의 제곱근(Math.sqrt(val))까지 나누어 떨어지는지 확인하고 나누어 떨어지면 메서드를 종료시켜 다음 수를 받아 검사한다.
   끝까지 나누어 떨어지는 수가 없다면, 입력 받은 val값을 StringBuilder(sb)에 append하고 개행한다.
   
   
4. 모두 확인해보고 최종적으로 소수만이 담긴 sb를 출력하여준다.

6. Code 💻

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


public class Main {
	static StringBuilder sb = new StringBuilder();
	static public void get_prime(int val) {
		
		if(val < 2) {
			return;
		}
		
		if(val == 2) {
			sb.append(val).append("\n");
			return;
		}
		
		for(int i=2; i<=Math.sqrt(val); i++) {
			if(val % i == 0) {
				return;
			}
		}
		sb.append(val).append("\n");
	}

	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());
		
		for(int i=M; i<=N; i++) {
			get_prime(i);
		}
		
		System.out.println(sb);
	}

}

7. Growth 🍄

[ 소수를 판별하는 방법 ]

[ 방법 1 ] 2부터 N보다 작은 수들을 모두 나누어보기.

• 소수는 자연수 N이 1과 자기 자신만으로 나누어 떨어져야한다.
  그러므로 자기 자신보다 작은 숫자들 중에서 어떤 수와도 나누어지면 소수가 아니게 된다.

[ 방법 2 ] 2부터 제곱근 N (Math.sqrt(N))까지의 수들을 나누어보기.

• 이 방법은 a x b = N 일 때, a 또는 b는 N의 제곱근을 기준으로 서로 반비례한 값을 가지는데
  예를 들어,

< N = 16 > 일 때,

a	b
1	16
2	8
4	4
8	2
16	1

이므로 제곱근까지 나누어지는 수가 존재하다면 그 수는 소수가 아니게 된다.
[ 방법 1 ] 보다 훨씬 더 적은 값들을 확인하므로 보다 빠르게 판별할 수 있다.

[ 방법 3 ] 에라토스테네스의 체 (eratosthenes)

• 2의 배수들을 제거한다. (2는 제외)
• 3의 배수들을 제거한다. (3은 제외)
• 5의 배수들을 제거한다. (5는 제외)
• 7의 배수들을 제거한다. (7은 제외)
  다 제거되고 나면 남아있는 값들은 소수의 특징을 가지는데

* 단, 120이하인 경우에서만 적용이 가능하다

---

에라토스테네스의 체로 문제를계속 출력 초과가 나왔다.
한참 헤매다가 질문 검색에 다른 사람 풀이에 121을 넣어보라해서 넣어보았더니
121[1, 11, 121] 소수가 아님에도 계속 출력 되었다.
에라토스테네스의 체는 120 미만의 소수들만 판별할 수 있음을 이번 알고리즘 문제를 통해 깨달았다.