소수를 구하는 방법 - 에라토스테네스의 체
i = 2부터 √N 이하까지 반복하여 자연수들 중 i를 제외한 i의 배수들을 제외시킨다.
- 소수를 판별할 범위만큼 배열을 할당해 그 인덱스에 해당하는 값을 넣어줌
- 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지움 (2, 3, 5등의 자기 자신은 지우지 않음). 이미 지워진 숫자는 건너뜀.
i = 2, 3, 5 등등 일 때의 배수를 모두 지워서 i = √N까지 반복하는 방법
구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Prime {
// 소수를 체크할 배열
public static boolean[] prime;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
make_prime(N);
}
public static void make_prime(int N) {
// 0 ~ N
prime = new boolean[N + 1];
// 처음엔 모든 수가 소수 (true)인 것으로 초기화 (0, 1제외)
Arrays.fill(prime, true);
// 에라토스테네스의 체 알고리즘 수행
// 2부터 n의 제곱근까지 모든 수 확인하기
for (int i = 2; i <= Math.sqrt(N); i++) {
// i가 소수인 경우 (남은 수인 경우)
if (arr[i] == true) {
// i를 제외한 i의 모든 배수 지우기
int j = 2;
while (i * j <= N) {
prime[i * j] = false;
j += 1;
}
}
}
// 모든 소수 출력하기
for (int i = 2; i <= N; i++) {
if (prime[i]) System.out.print(i + " ");
}
}
}
시간복잡도
- O(NloglogN)
- 선형 시간에 가까울 정도로 매우 빠름
- 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있음
- 하지만 각 자연수에 대한 소수 여부를 저장해야하므로 메모리가 많이 필요함.
Reference
JAVA [자바] - 소수 구하는 알고리즘 및 구현
[이것이 코딩 테스트다 with Python] 38강 에라토스테네스의 체
