[알고리즘] 소수 알고리즘(에스토스테네스 체)

에스토스테네스 체

  -> 소수를 구할 때 사용하는 가장 최적화된 알고리즘이다.

 

알고리즘 설명

   1 ) 먼저 일차원 배열을 하나 만든다.

   2 ) Ch[i] == 0이면 ch[i] = 1로 바꾸고 ch[i]의 배수도 모두 1로 바꾼다. 

 

Ex ) i = 2일 때, ch[2] == 0이다. 따라서 값을 1로 바꾸고 2의 배수인 4,6,8,10,12,14도 1로 바꾼다. 

       i = 3일 때, ch[3] == 0이다. 따라서 값을 1로 바꾸고 3의 배수인 6,9,12도 값을 1로 바꾼다.

       i = 4일 때, ch[4] == 1이다. 즉 소수가 아니다. 따라서 그냥 넘어간다.

 

 

구현

   코드 구현은 다음과 같다.(자바)

int cnt=0;
int[] ch = new int[n+1];
for(int i=2; i<=n; i++){
	if(ch[i]==0){
		for(int j=i; j<=n; j=j+i) ch[j]=1;
	}
}