[Algorithm] 에라토스테네스 체

그냥 하던대로 풀어도 되지 않을까?

for(int i=2;i<n;i++)
{
	if(target%i == 0)
		return false;
}
return true

 기존의 소수문제를 풀이하다 보면 단순하게 1씩 증가시키면서 해당 숫자가 나누어 떨어지는지 확인하는 방법을 사용하곤 하였다. 숫자의 범위가 작은 경우 크게 문제 되는 풀이는 아니다. 하지만 코딩테스트에 출제 된 문제들의 경우 말이 달라진다. 일단 숫자의 범위도 클 뿐더러 소수 구하는 부분에서 속도를 다 잡아 먹게 되면 다른 부분의 풀이가 아무리 빠르더라도 시간초과 오류로 인해 정답 패스가 되지 않는다. 특히 단순하게 소수만 구해라는 문제는 잘 출제 되어지지 않았던 걸로 기억한다. 해당 풀이 말고 소수와 관련된 풀이는 다양하게 존재하니 차차 업데이트 하기로 하고 지금 현재 주제인 아라토니스체의 풀이 방법을 알아보고자 한다.

위키피디아의 설명 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

출처 :

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

// boolean[] primeArr = new boolean[N];
for(int i=2; (i*2)<=n; i++){
	if(!primeArr[i]){
		for(int j = i*2; j<=n; j+=i) 
        	primeArr[j] = true;
		//i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다.
	}
}

 

추가 설명

코드 블럭에서 N에 해당하는것이 소수를 구할때의 범위라고 한다면 N의 범위 아래에있는 모든 소수의 집합을 구할 수 있다. 이런 사실을 바탕으로 소스를 보았을 때 첫번째 if문이 소수라 판별이 되면 해당 소수의 배수는 모두 삭제 할 수있다. 추가적으로 for문에서 j=i*2인 부분은 원래라면 j=i*i 가 맞으나 제곱을 하게 되었을때 범위가 너무커져 int 자료형의 메모리가 감당을 못하기에 i*2로 변경 된 것임을 확인하자. 

첫번째 루프를 f1 이라 하고 두번째 루프를 f2 라정의하자
f1 -> i =2 ; (i=2) * (i=2) <= N 
f2 -> j = (i=2) * (i=2) ; j <=N
                Loop -> j = 4 primeArr[4] = true  ||   j+(i=2)
                Loop -> j = 6 primeArr[6] = true  ||    j+(i=2)

...........

                Loop -> j = 100 primeArr[100] = ture  ||    j+(i=2)

f1 -> i=3 ; (i=3) * (i=3) <=N
f2 -> j = (i=3) * (i=3) ; j <=N
                Loop -> j = 9 primeArr[4] = true  ||    j+(i=3)
                Loop -> j = 12 primeArr[6] = true  ||    j+(i=3)

...........

                Loop -> j = 99 primeArr[99] = ture  ||    j+(i=3)

 

코드로 바로 이해가 안갈 수도 있다.!! 그럴땐 쓰자... 몇번 적다보면 이게 왜 맞는 이론인지 몸의 피로로 깨우치게 된다.

적용문제:

https://saltae.tistory.com/16

[프로그래머스] 소수 찾기 [JAVA]