[소수판별]에라토스테네스의 체

이 글은 Java Language에 기반합니다.

에라토스테네스란?

> 에라토스테네스는 소수 판정문을 이용하는 구문에서
대량의 소수 데이터가 필요할 때 사용하는 방식이다.

시간복잡도

> O(NlogNlogN)
사실상 선형 시간에 가까우며 작은 소수 판정문에서도
용이하지만 대량으로 가면 갈 수록 그 속도가 현격히
빨라져 자주 이용한다.

장점

> 위에서 계속 언급했듯이 기본적으로 속도가 빠르며 대량 소수 판정문에서 가장 효율이 높다.

단점

> 1부터 계산 범위까지의 모든 숫자를 다 배열에 넣고,
소수가 아닌 부분을 0으로 변경하는 과정을 거치기 때문에
메모리 용량이 많이 필요하다.

예시 코드

int[] Array = new int[N];
for(int i = 2; i <= N; i++) {
	Array[i] = i;
}

for(int i = 2; i <= N; i++) {
	for(int j = i * 2; j <= N; j += i) {
		Array[j] = 0;
	}
}