[알고리즘] 에라토스테네스의 체 자바 java 소수 판별

 

 

 

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int t = Integer.parseInt(reader.readLine());

		boolean[] b = new boolean[t + 1]; // 1

		b[0] = b[1] = false; // 2
		for (int i = 2; i <= t; i++) { // 3
			b[i] = true;
		}

		int sq = (int) Math.ceil(Math.sqrt(t)); // 4

		for (int i = 2; i <= sq; i++) { // 5
			if (!b[i]) // 6
				continue;
			for (int j = i * i; j <= t; j += i) { // 7
				b[j] = false;
			}
		}

		for (int i = 2; i <= t; i++) { // 8
			if (b[i])
				writer.write(i + " ");
		}

		writer.flush();
		writer.close();
		reader.close();

	}

}

 

 

일명 소수 판별 문제이다. 소수 판별 문제는 크게 3가지가 있다.

 

첫번째는 그냥 반복문 중첩해서 각 수마다 2부터 올려가면서 나누다가 나눠떨어지면 소수가 아님으로 판별

 

두번째는 발견된 소수만 ArrayList에 담아두고 그 소수를 각 수를 나눠본 후 나눠지면 소수가 아님으로 판별

 

세번째는 위의 에라토스테네스의 체다.

 

첫번째 방법은 속도가 느리다. 물론 break문으로 속도를 올릴 수 있지만 두번째 방법보다 느리다. 

 

가장 좋은 방법은 위의 방법으로 두번째 방법보다 몇배는 빠르다

 

 

 

주석 참고하면 될 것 같다.

 

1. 배열 생성

 

2. 0과 1은 소수 판별의 대상이 아니므로 false 처리 true가 소수이다.

 

3. 먼저 모두 소수라고 가정하고 시작

 

4. 소수는 n의 배수가 아니어야 한다. 입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다.

그러나 모두 나누어볼 필요없이 루트 n 까지만 나누어서 떨어지면 소수가 아니다. 라는 수학적 정의를 이용하면 입력받은 수의 제곱근까지만 판별해보면 모든 소수를 구할 수 있다는 명제가 나온다.

 

5. 위에서 계산한 제곱근으로 반복문에 제한을 둔다.

 

6. 7.에서 미리 false로 처리된 수들은 판별할 것도 없이 소수가 아니므로 continue로 이동한다.

 

7. i의 값의 배수를 모두 false처리해서 소수가 아님을 나타낸다.

 

8. 출력한다.

 

 

 

폰노이만 같은 천재가 아닌 이상 내 마음대로 구현은 된다고 정답이라고 알고 있으면 우물안의 개구리가 된다.