에라토스테네스의 체

소수를 구하는 문제에서 가장 흔히, 쉽게 찾아낼 수 있는 방법으로는 에라토스테네스의 체가 있다.

 

에라토스테네스의 체를 코드에서 적용하는 방법을 설명하자면...

 

1. 먼저, 구하고자 하는 범위의 boolean형 배열을 만든다.

(만약 구하고자 하는 범위가 1~150 중의 소수라면 arr[151])

 

2. 이 arr 배열을 true나 false로 초기화시켜주고 그것을 소수라고 생각하자.

(boolean형 배열은 정의만 해둔다면 내부 element들은 모두 false로 초기화되어 있다.

그러므로 이를 고려해서 false를 소수라고 두면 간편할 수 있다.)

 

3. 이때, false를 소수로 정의해두고(즉, 모든 수가 소수라고 설정을 해둔 후) arr[1]만 true(소수X)로 변경해준다.(1은 소수가 아니니까)

 

4. 2부터 최대값(150)을 넘지 않는 제곱수(12*12)까지 변수 i로 설정하여 for문을 돌리고 그 안에서는 i가 소수인지 아닌지 확인을 하여 소수이면 5.를 진행, 소수가 아닐 경우엔 넘어간다. 

(이때, 왜 2부터 하나요? 소수의 정의가 나 자신과 1만이 약수인 수이므로 1을 가지고 굳이 소수 판단을 할 필요가 없을 뿐더러 이미 1이 소수가 아니라고 위에서 정의해두었으므로(arr[1]=true;) 포함해도 진행이 안된다.)

(이때, 왜 최대값을 넘지 않는 제곱수인가요? 이때 13*13인 경우를 보자. i가 13일 때 즉, 13부터는 소수 판단을 안해주어도 된다는 뜻이다. 이미 해주었다. 13*(13미만의 수)에서는 이미 (13이하의 수)의 배수들을 걸러내는 과정에서 걸러진다. 그러므로 13*(13이상의 수)들은 내가 구하고자 하는 범위를 초과하므로 구할 필요가 없다.)

 

5. i*i부터 N까지 변수 j로 설정하여 i씩 증가하는 for문을 돌리는데 이때 시작이 i*i인 이유는 i*1~i*(i-1)까지는 이미 앞에서 소수 여부를 확인했기 때문이다.

(ex) i = 5일 때, 5*1은 원래 소수, 5*2는 이미 2*5에서, 5*3은 이미 3*5에서, 5*4는 이미 2*10에서 검사를 진행하였음.)

(ex) i = 4일 때, 는 할 수가 없는데 이미 i=4가 소수가 아니라는 것을 i = 2*2에서 걸러냈기 때문임.)

 

6. 이후 이 for문을 돌려 모든 j값에 대해 그 인덱스 값을 갖는 arr배열 element들은 true(소수x)로 설정한다.

 

<4. ~ 6. 에 대한 코드 구현 내용>

for(int i=2; i*i<=N; i++){
	if(!prime[i]){
		for(int j=i*i; j<=N; j+=i) prime[j]=true;                
	}
}

 

7. 이렇게 설정들이 끝났다면 내가 원하는 수들에 대한 소수 여부 검사는 arr이라는 배열이 판독기가 되어 걸러줄 것이다.

 

 

에라토스테네스의 체는 모두 소수로 정의해두고 아닌 부분들에 대해서 걸러주어 정답지를 만들어두는 방식이다.

물론 소수를 걸러내는 중간 과정에서 미리 소수를 검사한 내용을 적용하여 출력할 수 있지만, 모든 과정을 마친 후에는 소수를 찾아낸 정답지를 생성해낸다.

이때, 가장 중요한 것은 for문 내의 변수 i와 j의 범위를 설정하는 부분과 arr[1] = true와 같이 미리 소수가 아닌 1을 빼두는 것이다.