소수 판별하기, 2002

일반적으로 소수를 판별하는 다항식은 존재하지 않는다고 많이 알려져 있습니다. 그래서 소수를 판별하는 것 또한 컴퓨터로 하기 힘든 일 중에 하나죠. 최근 그 문제에 대한 해답이 나왔나 봅니다. 소수를 판별하는 다항식에 대한 자세한 설명과 알고리즘이 나와 있습니다.

http://www.cse.iitk.ac.in/news/primality.pdf [1]

기럼, 전 구시대적 방법으로 판별하는 함수를 하나 올리도록 할께염… ㅎㅎ

int IsPrime(int n)
{
   int i;
   for(i=2; i<n; ++i)
       if(n % i == 0)
            return 0; 

   return true;
}

이 소스는 위의 함수를 이용하여서 1000이하의 소스를 출력하는 소스 입니다.

int i; 

for(i=0; i<1000; ++i)
{
   if(IsPrime(i))
        printf("%d ", i); 

   if((i+1) % 7 == 0)
        printf("\n");
}

[1] 링크가 깨졌네요. 글에서 언급한 소수 판별 다항 알고리즘은 “AKS 소수 판별법”입니다. 다음 위키 페이지에 설명이 나와 있습니다. http://en.wikipedia.org/wiki/AKS_primality_test

소수라고 함은..정수로 하는 것인데..쓸대 없이 루프가 더 도네요….정수는 자신의 1/2 이상의 수로는 절대 나눌수 가 없죠….. for(i = 2; i < n/2 ; ++1) 라고 해야…효율적일듯

by 까칠한 인터넷 논객

n/2라뇨. 수학을 배웠으면 루트죠. 이게 더 효율적일듯…

double
MyRoot(int n)
{
   double x;
   x = (double)n; 

   return sqrt(x);
} 

int
IsPrime(int n)
{
   int i; 

   for(i=2;i<=MyRoot(n);i++)
   {
       if(n%i == 0)
          return FALSE;
   } 

   return TRUE;
}

by 까칠한 인터넷 논객 제압자

안녕하세요,

ICPC 자료들 구하다가 찾아들어왔습니다.

좋은 자료 잘 받아갑니다.^^;

마지막으로 올라온 코드에서 한가지 더 추가드리자면..

n이 짝수일때는 소수일리가 없으므로..
int
IsPrime(int n)
{
   int i; 

   for(i=2;i<=MyRoot(n);i+2) // increment i by 2
   {
       if(n%i == 0)
          return FALSE;
   } 

   return TRUE;
}
그리고 위의 함수는 아래의 매크로로 사용될수 있습니다. (단 n이 홀수일때만).
#define isprime(n) (a[(n)>>4]&(1<<((n)>>1)&7)) //works when n is odd
글구…

위에 예제처럼 primality testing을 여러번 해야 할 시에는 sieve라는 알고리즘을 많이 사용합니다. 테이블을 0부터 n까지 잡고, 각 숫자마다 2부터 sqrt(n) 까지만 테스팅을 해주는 방식인데요, 그걸 해주자면 배열에서 루프를 돌려서 각 인덱스마다 인덱스의 배수에 해당하는 엘리먼트들을 죄다 날려주는 겁니다. 이런식으로 날려(?)주다보면 나중엔 안날라(?) 간 아이들만 소수가 되는것이지요.. 간단한 코드 올려 봅니다.
#define MAX 20000000
char sieve[MAX+1]; 

void gen_sieve(void) {
  /*sieve: 0 means prime, 1 means composite*/
  int i, ulimit,j;
  memset(sieve, 0x00, 20000001);
  sieve[1]=1;
  sieve[2]=0;
  for(i=4;i<(MAX+1);i=i+2)
    sieve[i]=1;
  sieve[3]=0;
  for(i=6;i<(MAX+1);i=i+3)
    sieve[i]=1;
  ulimit=sqrt(MAX)+1;
  for(i=3;i<ulimit;i=i+2) {
    if(sieve[i]==0) {
      for(j=2*i;j<(MAX+1);j=j+i)
        sieve[j]=1;
    }
  }
}
위 알고리즘의 시간복잡도는 O(n log log n )입니다.

시간 복잡도 계산을 위해선 다음과 같이 생긴 harmonic series를 구해야 합니다.

Sigma n/i, i=3..sqrt(n), where i=prime number

ie) n/3 + n/5 + n/7 + n/11 + n/13 + …

그리구 저 시리즈의 값은 다음 주소에 나와있네요.^^;

http://mathworld.wolfram.com/MertensSecondTheorem.html

by 인터넷 지존