[C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체

http://marobiana.tistory.com/91

소수 구하기 최적의 알고리즘 1편에서 (http://marobiana.tistory.com/89) 

주어진 수보다 작은 수의 소수들로 나누는게 성능이 좋다고 했었는데,

그것보다 더 좋은 알고리즘을 찾아냈다.ㅋㅋ

이것보다 더 좋은 방법은 아마도 없을 것이라 자신함 !! 

만약 있다면 댓글 달아주시기 바람.

요번에는 c++로 구현해보았음.

1. 알고리즘

에라토스테네스의 체 (Sieve of Eratosthenes)라는 알고리즘이다.

아래 그림을 보면 무엇인지 알 수 있다.

120까지의 모든 소수를 구한다고 해보자.

 

2부터 120까지 배열에 모두 넣은 후

소수가 아닌 것들을 모두 체크해버리는 것이다.

2를 제외한 모든 2의 배수를 체크한다.

3을 제외한 모든 3의 배수를 체크한다.

4는 아까 체크당했으므로 소수 아님.

5를 제외한 모든 5의 배수를 체크한다.

......

체크가 안된 수들이 소수이다.

이 알고리즘을 이용하면, 최악과 최선의 프로그램을 만들어낼 수 있다.

2. 예제

에라토스테네스의 체를 이용해서 구현을 해보겠다.(에라토스테네스...이름 겁나 안외워지는군ㅋㅋㅋㅋㅋㅋ

void getChe1(int num) {     int *arr;     arr = (int *) malloc(sizeof(int) * num);          // 입력받은 수 만큼 배열에 모두 초기화 해둔다     for (int i = 2; i <= num; i++) {         arr[i] = i;     }          for (int i = 2; i <= num; i++) {  // 나누는 값 : i         for (int j = 2; j <= num; j++) {             if (arr[j] != i && arr[j] % i == 0) {  // 자신과 같지않고 0으로 떨어지면 소수아님                 arr[j] = 0; // 소수가 아닌 경우 0을 넣어둔다             }         }     }          // 출력     for (int i = 2; i<= num; i++) {         if (arr[i] != 0)                cout << arr[i] << " ";     } } int main(void) {     clock_t start, end;          start = clock();     getChe1(50000);     end = clock();          double time = (double)(end - start) / CLOCKS_PER_SEC;      cout << "수행시간 : " << time; }

결과 및 수행시간 >>

어마어마하다. 18초나 걸렸다... ㅋㅋㅋ

1편에서 구현했던 최악의 알고리즘의 3배정도의 시간이 걸렸다.

1편의 최악의 알고리즘의 시간은 아래와 같았다. 6.07415초..

하지만, 에라토스테네스의 체를 잘 이용하면 최상의 소수 구하기 프로그램을 만들 수 있다.

최적의 방법을 생각해내보자..

그것은 바로!

체크할 때, 모든 수를 다 돌면서 체크할 필요 없이

체크 할 배수만큼만 반복문을 돌게하는 것이다.

그리고, 이미 0으로 체크되어버린 수의 배수는 확인하지 않는다.

(왜냐면, 체크된 수의 배수들도 이미 다 체크가 되어있기 때문이다)

예제 >>

void getChe(int num) {     int *arr;     arr = (int *)malloc(sizeof(int) * num);     int i = 2;     // 입력받은 수 만큼 배열에 모두 초기화 해둔다     for (i = 2; i <= num; i++) {         arr[i] = i;     }          for (i = 2; i <= num; i++) {          if (arr[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다             continue;         for (int j = i + i; j <= num; j += i) { // i를 제외한 i의 배수들은 0으로 체크             arr[j] = 0;         }     }     // print     for (i = 2; i <= num; i++) {         if (arr[i] != 0)             cout << arr[i] << " ";     } }

결과 및 수행시간 >>

확 줄었다!! 심지어 1초도 안걸린다.

1편에서 최적의 알고리즘이라고 했던, 특정 수보다 작은 소수들로 나누어보는 알고리즘의 속도는

아래와 같았었다.

이것도 1초는 안걸리지만 에라토스테네스의 체를 이용한 것보단 느린편이다.

그리고 추가적으로..

조금 더 좋게 해보기위해 수학의 공식도 이용을 해보았다 ㅋㅋ

수학자들에 의해 이미 증명된 공식. 좀 간단히 설명하자면,

소수는 n의 배수가 아니어야 한다. 입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다. 그러나 모두 나누어볼 필요없이, 루트 n 까지만 나누어서 떨어지면 소수가 아니다.

이 이론을 위의 예제와 접목해보면 아래같이 할 수 있다.

나눌 수를 루트 num까지만 돌리는 것~!

for (i = 2; i <= sqrt(num); i++) {          if (arr[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다             continue;         for (int j = i + i; j <= num; j += i) { // i를 제외한 i의 배수들은 0으로 체크             arr[j] = 0;         }     }

수행 시간은 아래와 같다.

루트 씌우기 전엔 0.0006489초 였으니 아주 미세한 차이지만 조~~금 더 줄었다 : )