[Numerical Analysis][C] 에라토스테네스의 체 ( Eratosthenes' sieve ) 에 의한 소수판별

n이 소수이면 1을 리턴하고, 아니면 0 을 리턴하는 함수를 만들어보자.

int isprime(unsigned long n)
{
      unsigned long  i ;

      for(i=2;i<=sqrt((double)n);i++) {       // root n 이하의 모든 정수에 대해 인수 없으면, 소수임.
            if((n%i)==0)                                  
                 return 0;
      }

      return 1;
}

물론 퍼레미러로 넘어오는 변수의 범위가 적절하도록 제약을 가해주는 것이 바람직하며, sqrt() 는 math.h 를 include 하던가, 아니면 int 형 인자를 받도록 직접 만들고, 캐스트를 없애줘도 된다.

위의 함수를 이용한 소수판별 프로그램을 첨부한다.

isprime.exe

아래는 실행화면이다.

참고로, 너무 큰 정수는 오버플로우가 나서 안되고, 적당히(?) 작은 숫자까지만 된다. 더 큰숫자를 사용하고싶으면, 스트링을 사용해서 원하는 만큼 긴 정수를 다룰수 있다.

-------------------------------------------------------------------------------------------

위의 코드를 보면, 에라토스테네스의 체로 소수판별할때 n 에 대해, root n 이하의 정수까지만 나눠떨어지는 게 있는지 검사하면 충분한데, 간단한 문제이니,  왜 그런지 직접 증명해보길 권한다.