[알고리즘] 에라토스테네스의 체 ( 소수 구하기 )

사실 소수를 구할 때 간단하게 생각한다면 이렇게 구현할 수 있을 것이다.

bool isPrimeNumber(int a){
	for(int i = 2 ; i < a ; i++){
		if(a % i == 0){
			return false;
		}
	}	
	return true;	// 소수일경우  
}

하지만 위와 같은 알고리즘의 시간 복잡도는 O(N)이다. 모든 경우의 수를 다 돌며 약수 여부를 확인한다는 점에서 몹시 비효율적이다. 하지만 에라토스테네스의 체를 이용한다면 한 두개의 소수를 판별하는 게 아니라 대량의 소수를 한꺼번에 판별하기에 용이하다.

int MAX=120;
		
boolean [] primeNum=new boolean[MAX+1];
		
for(int i=2; i<=MAX; i++) {
	for(int j=2; i*j<=MAX; j++) {
		primeNum[i*j]=true;
	}
}
		
for(int i=2; i<=MAX; i++) {
	if(!primeNum[i]) System.out.print(i+" ");
}

 

에라토스테네스의 체의 시간 복잡도는 O(n long long n )이다.

 

참고

• 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