메뉴 건너뛰기


Computer Science > Algorithm

기타 에라토스테네스의 체

2013.12.28 03:32

푸우 조회 수:12352


* @ 설명
* 소수란 다음과 같이 1과 자기 자신 외에는 약수를 갖지 않는 수를 말한다.
* 2, 3, 5, 7, 11 ...
*
* n 이 소수인지 아닌지는 n이 n 외의 저수로 나누어 떨어지는지 아닌지를
* 통해서 알 수 있다. n 이하의 정수에서 2까지 수로 나누어서 떨어지는 수가
* 있으면 소수가 아니므로 루프에서 빠져 나오면 된다. 루프의 끝까지 수행해도
* 나누어 떨어지지 않으면 그 수는 소수이다. 또한 n은 n/2이상의 정수로 나누어
* 떨어지지 않으므로 시작값은 n이 아니라 n/2값부터라는 것을 알 수 있다.
* (수학적으로는 n의 제곱근부터 시작해도 된다고 알려져 있다.)
*
* */
#include <stdio.h>
#include <math.h>
int main(void)
{
    int i, n, Limit;
    while(printf("\nInput Data : "),scanf("%d",&n) != EOF){
        if(n>=2){
            Limit = (int)sqrt(n);
            for(i=Limit;i>1;i--){
                if(n%i == 0) break;
            }
            if(i==1)
                printf("소수");
            else
                printf("소수아님");
        }
    }
    return 0;
}



/*
* 에라토스테네스의 체 알고리즘은 다음과 같다.
*
* 1. 2와 n사이의 수를 모두 체에 넣는다.
* 2. 체에서 최소값을 소수로 지정한다.
* 3. 방금 구한 소수의 배수를 체에서 모두 제거한다.
* 4. 2번과 3번을 n까지 반복했을 때 체에 남은 수가 소수다.
*
* */
#include <stdio.h>
#include <math.h>
#define NUM 1000
int main(void)
{
    // static 선언자는 프로그램이 종료할때까지 사라지지도 않고
    // 초기화도 두번이상 이루어 지지않는다.
    static int prime[NUM /2+1];
    int i, n, m=0, Limit;
    for(n=2;n<=NUM ;n++){
        Limit = (int)sqrt(n);
        for(i=Limit;i>1;i--){
             if(n%i == 0) break;
        }
        if(i==1) prime[m++]=n;
    }
    printf("2~%d 사이의 소수\n",NUM );
    for(i=0;i<m;i++){
        printf("%5d",prime[i]);
    }
    printf("\n");
    return 0;
}


[출처] 에라토스테네스의 체 |작성자 카페모카



이전 게시판에 댓글이 적혔는데 보관할 가치가 있어보여 댓글도 옮겨옵니다.


실용프로그… 09-03-13 12:14
  
수학과 프로그램은 비슷하지만 다르다. 
수학적으로 빠른 것이 프로그램상에서 빠른 것은 아니다. 
실제 위의 두 개의 알고리즘을 가지고 시간계측해 보라. 
시간 복잡도에 의한 계산을 얘기하는 것이 아니다.  실제 해상도 높은 타이머를 이용해서 호출 전과 호출 후의 계측값의 차를 살펴보라.  과연 얼마가 되어야 에라토스테네스의 체가 빠른가?  
int형의 숫자 범위내에서는 절대 빠르지 않다.  
프로그램상에서 에라토스테네스의 체의 알고리즘을 적용하는 것은 결코 빠르지 않다. 

그런다 하더라도 '논리적 사고력을 키우는 데에는 이러한 트레이닝은 효과적이다'라는 데에는 공감한다.

     
푸우 09-03-13 13:37
  
위의 글은 제가 네이버 블로그에서 옮겨온 것인데... 
옮겨올때는 잘 구현되어 있겠지 하면서 옮겨왔는데... 
나중에 사용해 볼려고 하다보니깐... 에라토스테네스의 체 이론의 장점이 그대로 적용된 것은 아닌것으로 보입니다. 
언젠가 내가 장점들을 살려서 다시 짜서 올려야지 했는데... 
게을러서 시간만 흐르네요. 
아무튼 좋은 지적 감사합니다.