소수 구하기 (Prime number)

소수 (Prime number)

 

글. 오상문 sualchi@daum.net

 

소수는 1과 자신 이외에는 나누어 떨어지는 수가 없는 수이다.

 

[참고] 반대로 1과 자신 이외에 나누어 떨어지는 수가 있으면 합성수라고 부른다.

 

 

(방법1) 2부터 나머지 연산을 검사하기

 

소수를 구하는 가장 가단한 방법은 2부터 그 수의 1/2 부분까지 계속 나머지 연산을 해서 0이 나오는지 검사하는 것이다. 그 이후는 어차피 나머지가 0보다 크므로 계산할 필요가 없다. 

 

예를 들어, 10237이 소수인지 검사할 때 

2~5119까지만 나머지 계산을 해서 0이 되면 소수라고 처리한다.  

 

isPrime(unsigned int) {

  for(i=2; i <= n/2; i++) {

    if(n%i == 0)

      return 1;

  }

  retrun 0;

}   

 

int main()

{

  if(isPrime(10237))

    printf("소수\n");

  else

    printf("소수 아님\n"); 

 

  return 0;

}

 

 

(방법2) 2, 3 배수를 제외해서 계산량 줄이기

 

#include <stdio.h>
int isPrime(unsigned int num); // 소수 68906개, 180초

 

int main(void)
{
  unsigned int i, cnt=0;

  for (i = 100000; i < 1000000; i++)
    if (isPrime(i)==1) printf("%u\n", i), cnt++;
   
  printf("count: %u\n", cnt);
  return 0;
}

 

int isPrime(unsigned int num)
{
  unsigned int i;
  unsigned int y = 2;
  unsigned int x;

 

  if (num<1) 0;  // 1 이하는 소수 아님
  if (num==2 || num==3) return 1;  // 2,3은 소수
  if (num%2==0 || num%3==0) return 0; // 2와 3의 배수는 소수 아님

 

  for (i = 5; i <= num/2; i++)
    if (num%i == 0) return 0;

  return 1;
}

 

(방법 3) 좀더 복잡한 방법... 6의 배수에서 -1. +1인 숫자인지 확인하는 구별법이다. 

 

소수를 적어보면 5 이상의 소수들은 6의 배수에서 -1, +1인 숫자들이 많은 것을 알 수 있다. 이 규칙을 이용하여 소수를 판별하는 방법으로 이전에 사용한 방법보다 훨씬 빠르다.   

 

// 소수 68906개, 19초

int isPrime(unsigned int num)
{
  unsigned int i;
  unsigned int y = 2;
  unsigned int x;
 
  if (num<1) 0;  // 1 이하는 소수 아님
  if (num==2 || num==3) return 1;  // 2,3은 소수
  if (num%2==0 || num%3==0) return 0; // 2와 3의 배수는 소수 아님
 
  x = (unsigned int) sqrt((double)num);  // 제곱근 수를 이용

  for (i = 5; i <= x; i += y, y = 6 - y)    // 25~
    if (num%i == 0) return 0;

 

  return 1;
}

 

 

파이썬 코드는 다음과 같다.

 

int isPrime(unsigned int num)
{
  unsigned int i;
  unsigned int y = 2;
  unsigned int x;
 
  if (num<1) 0;  // 1 이하는 소수 아님
  if (num==2 || num==3) return 1;  // 2,3은 소수
  if (num%2==0 || num%3==0) return 0; // 2와 3의 배수는 소수 아님
 
  x = (unsigned int) sqrt((double)num);  // 제곱근 수를 이용

  for (i = 5; i <= x; i += y, y = 6 - y)    // 25~
    if (num%i == 0) return 0;

  return 1;
}

<이상>