백준 1929번
https://www.acmicpc.net/problem/1929

---

문제

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

---

생각하기

소수를 찾는 문제를 보고 바로 떠오른 한 가지 바로,
소수를 찾는 문제다? 무조건 에라토스테네스의 체!

에라토스테네스의 체
설명 참조

에라토스테네스의 체는 x라는 값이 소수인지를 판단하려고 할 때, 하나씩 반복하며 소수인지를 판별하는 것이 아니라 x의 루트를 씌운 값의 배수까지만 확인하면 된다는 방법이다.
x가 1000일때, 1000의 루트는 31.62277...으로 된다. 여기서 정수는 31이기 때문에 31 배수 까지만 확인하면 된다는 것을 의미한다.

예시를 들어 M 값이 1이고, N이 1000이 었을 때 우리는 1부터 1000까지의 수 중에서
소수의 값을 찾는다고 했을때, 에라토스테네스의 체를 활용하여 코드를 만들어 체로 걸러보자.

먼저 최대값 N의 루트값을 sqrt의 변수로 저장을 해준다 N이 1000이 었기 때문에
sqrt는 31값이 된다.

다음 첫번째 i for문은 1은 소수가 아니기 때문에 제외한다. 처음 arr배열을 생성하면 모든 값은 false 처리가 되어 있기때문에 소수가 아닌 0과 1을 생각하여 arr[0], arr[1] 은 true처리를 해주고 시작한다.

그리고 나서 i는 2부터 31까지 반복한다. 두 번째 for문 부터 조금 생각이 어려웠는데,
처음에는 i for문과 같이 돌리면 되겠다 생각했지만 생각해보면 나는 1000까지의 소수를 찾아야 되는데 i가 2였을때를 생각해보면 2의 배수로는 62가 최대치였다. 그리고 이렇게 돌리면 5나 7 같은 숫자는 소수로 빠지지 않고 전부 true처리가 되어 버리기 때문에 다른 방법을 생각해야 했다.
첫번째 반복문은 수정하지 않고 완성시키고 싶어서 두번 째 for문 수정만 하기로 했다.

그럼 다른 방법으로 두번 째 j for문을 N만큼 돌려볼까 라는 생각을 했지만 이것또한 i가 2이고 j가 1000일 경우 N의 범위인 1000까지의 소수를 구해야 하는데, i*j 값이 2000까지 올라가서 범위를 벗어나게 된다.

그러다가 생각난게 N/i만큼 돌린다면 첫번째 for문을 수정하지 않고 완성할 수 있겠다는 생각이 들었다.

이렇게 되면 j for문은 i가 2일경우 j는 500까지 반복하고,
arr[i*j]로 주게되면, 1000까지 숫자의 2의 배수를 모두 파악할 수 있게된다.

7같은 경우도 i가 7로 7의 배수를 찾을때, j는 최대 142까지 올라서
i*j = 994 까지의 7의 배수를 찾을 수 있다. 7은 소수인데 j가 2부터 시작이니 7은 건너뛰고 14부터 7의 배수를 찾기 시작한다.

이렇게 반복하면서 소수가 아닌값은 true처리 하고 소수인 값은 false처리 해준뒤 arr배열에서 false인 값만 반복하여 출력하면 소수를 구할 수 있다.

TMI

지금 까지 풀어본 문제 중 소수 문제 중에서는 가장 까다로웠던 것 같음..

최근에 라마누잔 영화를 보고 생각나서 넣은 썸네일

나도 좋아하는 일과 재능의 조화를 이룬 천재가 되고 싶다...
Like Will Hunting and Rāmānujan

---

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		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());
		int i;
		boolean arr[] = new boolean[N+1];
		arr[0] = arr[1] = true; // 0과 1은 소수에서 제외.

		// 에라토스테네스의 체 사용
		int sqrt = (int) Math.sqrt(N);
		for(i=2; i<=sqrt; i++) {

			for(int j=2; j<=N/i; j++) {
					if(arr[i*j] == true) {
						continue;
					}
					else  {
						arr[i*j] = true;
					}
			}	
		}

		for(i=M; i<=N; i++) {
			if(arr[i] == false) {
				System.out.println(i);
			}
		}
	}
}