정수론

소수

 이 토픽에서는 소수에 대한 다양한 수학적 특징들과 관련 알고리즘에 대해 알아봅니다. 소수에 대한 기본적인 정의는 아래와 같습니다. 간단하지만 중요한 정의이므로 꼭 숙지하시기 바랍니다.

 소수(prime number)는 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수로 정의된다. 정수론에서 매우 중요한 역할을 담당한다. 현재에 와서는 암호 분야에서의 사용으로 그 중요성이 부각되고 있다. (위키피디아 발췌)

 

 소수의 특징

 위의 정의만으로도 소수에 대한 다양한 특징들을 정리할 수 있습니다. 아래의 내용들은 소수의 중요한 특징들이므로 알아두는 것이 좋습니다.

  • 소수는 1보다 큰 자연수입니다. 즉, 1은 소수가 아닙니다.
  • 소수는 자기자신과 1만 약수로 가집니다. 즉, 소수는 약수가 딱 2개 있습니다. 역도 성립합니다.
  • 2는 소수입니다.
  • 하지만, 다른 모든 짝수는 2를 약수를 가지므로 소수가 아닙니다.
  • 2, 3을 제외한 모든 소수는 자연수 n에 대해 6n-1 혹은 6n+1 꼴입니다. 역은 성립하지 않습니다.

 

 소수의 판별

 위의 특징들을 활용하면 어떤 자연수 n에 대해 소수인지 아닌지 여부를 판별할 수 있습니다. 다음의 사항들을 차례로 검사해봅시다. 

  • 1은 소수가 아니다.
  • 2는 소수이다.
  • 2를 제외한 모든 짝수는 소수가 아니다.
  • 홀수는 2와 n-1사이에서 약수를 가지지 않는다. (1과 자기 자신만이 약수이기 때문)

 위의 과정을 코드로 표현하면 아래와 같습니다.

bool isPrime(int n)
{//정수 n이 소수이면 true를 반환한다.
    //1은 소수가 아니다
    if(n == 1) 
        return false;
    
    //짝수는 2이면 소수이다.
    if(n % 2 == 0)
        return (n==2);
        
    for(int i=3; i<n; i+=2)
    {// 2 ~ n-1 범위의 홀수 약수가 있는지 검사한다.
        //약수가 있다면 소수가 아니다.
        if(n % i == 0)
            return false;
    }
    //약수가 발견되지 않았으므로 소수이다.
    return true;
}

 

 위의 방법은 최악의 경우 n의 소수 여부를 판별하기 위해 대략 n/2개의 수에 대해 약수 여부를 조사해보게 됩니다. 그러므로 O(n)의 시간복잡도를 가지며 이는 상당히 느린 방식입니다. 위의 방식은 소수의 특징에 대한 이해를 돕기위해 설명해드렸으며 뒤에서는 조금 더 빠른 소수 판별 알고리즘들도 다루겠습니다.

댓글

댓글 본문
작성자
비밀번호
버전 관리
코딩몬스터
현재 버전
선택 버전
graphittie 자세히 보기