티스토리 뷰

소수 구하기 최적의 알고리즘 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초 였으니 아주 미세한 차이지만 조~~금 더 줄었다 : )



저작자 표시 비영리
신고
댓글
  • 프로필사진 .. i<=sqrt(num)

    i*i<=num
    2013.11.24 03:02 신고
  • 프로필사진 신매력 sqrt함수 쓰는 것보다 곱하기 연산이 좀 더 낫겠네요. 좋은 의견 감사합니다 : ) 2013.12.01 13:04 신고
  • 프로필사진 C언어 보이 전 '소수 구하기'에만 집중해서 코드가 굉장히 비효율적이에요. 좋은 참고 되었습니다~ 2014.03.25 02:30 신고
  • 프로필사진 박태영 정올 소수문제때문에 골머리 썩었는데...
    덕분에 한 시간동안의 고민이 막을 내리네요 orz 감사합니다.
    2014.04.23 06:09 신고
  • 프로필사진 행인 일반적으로 sqrt 함수는 최적화가 되어 있긴 해도 어느 정도의 정밀도를 요구하기 때문에
    위 예제에 사용하실 거라면 그에 맞게 새로 구현하는 것이 낫습니다.
    그리고 for문에서는 가급적 함수 호출을 하지 않는 것이 최적화의 기본입니다.
    int sqrtNum = sqrt(num);
    for (i = 2; i <= sqrtNum; i++) { ... }
    2014.07.27 20:42 신고
  • 프로필사진 신매력 for문 안에서는 함수를 안쓰는게 좋군요. 명심하겠습니다~! 2014.07.31 23:17 신고
  • 프로필사진 silver0r 위에분이 말해주신건
    int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for(int i = 0; i < array.length; i++){}
    이런 경우일 때 조건문에서 조건을 확인할 때 매번 호출되다보니까 말씀하신 것 같네요.
    for(int i =0, length = array.length; i < length; i++){}
    전 이런식으로 즐겨씁니다 ㅎㅎ
    2015.03.06 16:30 신고
  • 프로필사진 소수 제가 가능한한 최고 소수를 뽑아보고싶은데 이걸로는 불가능하려나요 ㅠ.ㅠ. 2015.05.13 02:29 신고
  • 프로필사진 학생1 알고리즘 공부하는 데에 많은 도움이 되었습니다. 감사합니다. 수학이랑 컴퓨터는 같이 배워두면 정말 시너지가 높은 것 같네요! 2016.08.07 18:30 신고
  • 프로필사진 밤밤 감사요 도움이되었습니다 2016.12.10 15:55 신고
  • 프로필사진 지나가다가 요즘 컴파일러가 그렇게 멍청하지 않은데..
    for(int i = 0; i < array.length; i++)........
    모든 함수가 그런건 아니지만 이런 경우 확인해보면 length함수가 매번 호출되는게 아니라 한 번만 호출되는 걸 알 수 있습니다. 성능 차이 없어요.
    2017.04.13 21:22 신고
  • 프로필사진 지나가는 행인 n을 나누는 최초의 소수는 루트 n 이하입니다.라는 사실을 사용하면 훨씬 더 줄일 수 있지 않을까요? 2017.05.18 23:19 신고
  • 프로필사진 참고하세요 2와 3을 제외하고는 소수는 다 6k+1 또는 6k-1 모양이니까 그 수들만 추가하고 6k+1 또는 6k-1은 5 이상의 소수로만 나누어지니까 5 이상의 소수만으로 나누게 해 주면 더 빨리 계산할 수 있을 것 같아요. 2017.06.06 16:32 신고
  • 프로필사진 신매력 와아.. 답변 감사합니다!! 수학적인 지식이 부족하여 이 공식은 생각치 못했었어요. 2017.06.16 17:30 신고
  • 프로필사진 이상준 전 위 코드를 자바로 구현하였는데 sqrt 함수를 쓰니 결과가 제대로 나오지 않아서 아래와 같은 방법을 썼습니다.
    수행시간이 훨씬 줄어드네요

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


    elapsed : 1280
    elapsed2 : 821 (sqrt 적용후)
    2017.08.15 07:01 신고
댓글쓰기 폼