[알고리즘] 에라토스테네스의 채

포스트를 작성하게된 계기
평소에 알고리즘 문제 풀이를 진행할 때, 소수 관련 문제는 많이 풀어보지 않았다. 제곱근을 이용해 소수를 구하는 방식을 주로 사용하였기에, 소수 관련 문제 난이도가 올라갈 수록 풀이에 어려움을 겪었다. 에라토스테네스의 채를 정리하여 다음에 소수 관련 문제를 맞이하였을 때 보다 효율적인 풀이를 작성하기 위해서 포스트를 작성하게 되었다.

에라토스테네스의 채

에라토스테네스의 채는 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 숫자 N 까지의 소수를 찾는데 아주 효율적인 방법이다.

에타토스테네스의 채는 다음과 같은 순서로 진행된다.

1. 2부터 N 까지의 수를 나열한다.
2. 2부터 시작하며 N까지, 자신의 배수를 지워나간다.
3. 지워지지 않은 수는 모두 소수이다.

이 방법을 코드로 옮기면 다음과 같다.

// 구하고자 하는 숫자 범위
int N = 120;
boolean prime[] = new boolean[N];
prime[0] = prime[1] = true;
        
for(int i=2; i*i<=N; i++){
	if(!prime[i]){
		for(int j=i*i; j<=N; j+=i) prime[j] = true;                
	}        
}