소수 판별기 ( Primality test )

소수 판별기를 만들어보려고 한다. 어떤 수 n이 소수인지 아닌지 판별해주는 것이다. 당연히 함수는 predicate이 될 것이다.

 

---

 

배경 설명

소수라는 것을 배우고서 제일 처음 배우는 판별법은 아마 에라토스테네스의 체 ( Sieve of Eratosthenes ) 일 것이다. 중학생 때였던 것 같다. 2부터 n까지의 자연수 ( 1은 소수가 아닌게 자명하니까 ) 중에 어떤 수가 소수임이 판명된다면 그 수의 배수들은 전부 합성수가 될테니 소수 후보들에서 제외되는 원리를 이용해서 소수들을 찾아낸다. 제일 작은 소수부터 시작해서 그 다음 큰 소수들을 찾아가며 2~n 집합해서 합성수들을 제외시켜나가다보면 집합 안의 모든 합성수들이 제외된다. 이를 조금 응용해보면 n 보다 작은 수들이 n을 나눌 수 없다면 ( n을 나눈 나머지가 0이 아니라면 ) n은 소수가 되는 것을 알 수 있다. 아래 사진을 보자.

조금만 더 생각해보자. 어떤 합성수 m을 인수분해 시켜보면 인수들의 곱이 항상 짝을 지어 나타난다. 12 = 2*6 = 3*4 이렇게 말이다. 이런 짝들의 작은 수들 중에 최댓값 M에 주목하자. 이 수보다 작은 자연수들을 가지고서 m을 나눠보면 인수들 짝을 다 찾을 수 있다. 합성수들을 관찰해서 M을 찾아내는 작업을 하다보면 M의 상계 규칙을 찾을 수 있다. M은 m의 제곱근보다 작거나 같다. 심지어 m이 제곱수 ( 4, 9, 16, 25, 36, 49, ... ) 인 경우만 M이 m의 제곱근과 같고 나머지들은 다 것보다 작다.

두 자연수의 산술 평균과 기하 평균 사이의 관계를 생각해보면서 찾을 수도 있다. 두 수의 곱이 일정한 경우 ( 합성수의 인수 곱들 ) 두 수의 합이 최소가 되는 경우, 두 수가 같은 경우가 우리가 찾는 경우가 된다. ( 이거 참 수식을 안쓰고 말로 풀어쓰려니 어렵다 )

무튼 2부터 n까지의 모든 수를 가지고서 n을 나눠볼 필요없이 2부터 n의 제곱근까지의 모든 수만 가지고서 n을 나눠보면서 n의 소수 판별을 할 수 있다는 걸 말하고 싶었다. 이 원리를 이용해서 소수를 판별할 것이다. 참고로 이 방법을 제곱근 판별법이라고 부른다.

---

[문제]

숫자 n 을 입력받아 소수인지, 아닌지 판별해서 결과를 출력하라.

[예시]

입력: 3

출력: 3 is not prime

def is_prime( n ) :
    if ( n < 2 ) or ( n%2 == 0 ) :
        return False
 
    sqn = int( n**(0.5) )
    flag = False
    for i in xrange(3, sqn+1, 2):
        flag |= ( n%i == 0 )
 
    return not flag

2,3 줄에서는 n의 범위에 따라 확정적으로 소수가 아닌 숫자들을 선제외시켰다. C언어에서처럼 파이썬에서도 비트연산이 가능했다면 n%2보단 n&1 이 더 빠른 연산일 것이므로 바꿔주면 좋다.

 

5 줄의 sqn은 n의 제곱근보다 작은 자연수 중에 가장 큰 수를 연산해 저장하게 된다.

 

6줄에서 flag를 False로 초기화시킨후, 7줄의 3~sqn 범위 안의 모든 홀수를 데리고서 flag를 갱신시킨다. 이때 flag는 3~sqn 범위 안의 숫자들이 n을 나눌 수 있는지 검사하게 된다. 범위 안의 숫자 중 어느 하나라도 n을 나눌 수 있다면 flag는 True가 된다. for 반복문 대신 while 반복문을 써서 flag가 갱신되면 곧장 반복을 종료시켜도 좋을 것 같다.

 

이 함수는 소수인지 아닌지 알려주는 함수이므로 flag와는 정반대의 결과를 알려주므로 not flag를 반환시키면 된다.

 

 

물론 2,3줄의 선처리 없이 7줄의 3~sqn 범위 대신 2~sqn으로 써도 결과는 똑같이 나온다.