에라토스테네스의 체
10억(1024 x 1024 x 1024) 까지의 소수를 확인할 때 필요한 메모리
1
boolean[] isPrime = new boolean[1024*1024*1024];
boolean형 10억개 -> 1byte * 1024 * 1024 * 1024 -> 1GB
힙메모리가 1GB 이상 필요함.
Q. 1 ~ 123456 소수 찾기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
final int MAX_N = 123456;
boolean[] isPrime = new boolean[MAX_N + 1];
Arrays.fill(isPrime, true);
isPrime[0] = false; // 0은 소수 X
isPrime[1] = false; // 1은 소수 X
IntStream.rangeClosed(2, MAX_N)
.filter(i -> isPrime[i] == true)
.forEach(i -> {
for (int j = i * 2; j <= MAX_N; j += i) isPrime[j] = false;
});
System.out.println(isPrime[7]); // true
이 기사는 저작권자의
CC BY 4.0
라이센스를 따릅니다.