에라토스테네스의 체 - 소수구하기

에라토스테네스의 체를 구하는 방식은

2부터 ~ N까지  증가하는 i 를 제외한 i 의 배수를 하나하나 지워가면서 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 log logn)이다.

 

소수를 한번에 구해야 하는 문제라면 에라토스테네츠의 체를 사용하는것이 좋겠다!!