에라토스테네스의 체(Java)

 

 

에라토스테네스의 체는 소수를 구하는 알고리즘으로 유명하다.

"소수가 되는 수의 배수를 지우면 남은 건 소수가 된다는 알고리즘이다."

 

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 소수가 되는 수의 배수를 지우면 남은 건 소수이다.
3. 2로 예를 들면 자기 자신을 제외한 2의 배수를 지운다.
4. 3도 2처럼 3 자기 자신을 제외한 3의 배수들을 지운다.
5. 특정 숫자만큼 이 과정을 반복한다.

 

 

 

 

 

에라토스테네스의 소수 찾기를 다시 간단히 정리해서 설명하면

 

i=2 일 때, 2를 제외한 2의 배수는 모두 2로 나뉘니 소수가 아니다.

 

 

---

 

import java.io.*;

public class PrimeNumber {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		boolean[] primeNumberArr = new boolean[N + 1];
		primeNumberArr = primeNumberChecked(primeNumberArr, N);

		for (int i = 1; i <= N; i++) {
			if (!primeNumberArr[i])
				System.out.println(i);
		}

	}

	static boolean[] primeNumberChecked(boolean[] b, int n) {
		b[0] = true; // 소수면 false, 소수가 아니면 true
		b[1] = true;

		for (int i = 2; i < Math.sqrt(n); i++) {
			if (!b[i]) {
				for (int j = i * i; j <= n; j += i) { // 2를 예를 들면 2를 제외한 2의 배수는 2로 나뉘어지니 소수가 아님
					b[j] = true;
				}
			}
		}
		return b;
	}
}

boolean 배열을 이용한 에라토스테네스의 체

 

 

50
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47

 

 

---

 

 

import java.util.Scanner;

public class PrimeNumber {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		int[] arr = new int[N + 1];

		for (int i = 0; i < arr.length; i++) {
			arr[i] = i;
		}
		arr[0] = 0;
		arr[1] = 0;
		for (int i = 2; i * i < arr.length; i++) {
			if (arr[i] != 0) {
				for (int j = i * i; j <= arr.length; j += i) {
					arr[j] = 0;
				}
			}
		}
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] != 0)
				System.out.println(arr[i]);
		}
	}

}

int형 배열을 이용한 에라토스테네스의 체

 

100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

 

 

 

 

 

 

---

참고하면 좋은 자료

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

 

 

커버사진

https://www.flaticon.com/kr/free-icon/algorithms_1753819

<a href="https://www.flaticon.com/kr/free-icons/" title="연산 아이콘">연산 아이콘  제작자: Flat Icons - Flaticon</a>