파이썬 자료구조와 알고리즘_소수

다음 예제에서는 세 가지 다른 방법으로 한 숫자가 소수(prime number)인지 판단한다. 수수란 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수다. 즉, 약수로 1과 자기 자신만을 가지는 수다. 첫 번째 함수는 브루트 포스(brute force), 즉 무차별 대입 방법을 사용한다. 두 번째 함수는 제곱근을 이용한다. 끝으로 마지막 함수는 확률론적 테스트와 페르마의 소정리(Fermat's little theorem)를 사용한다.

 

 

#finding_prime

import math
import random

 

def finding_prime(number):

    """ brute force(마구잡이/ 무차별 대입 방법) """

    num = abs(number)
    if num < 4 : return True

    """ 2에서 num까지의 연속된 수를 갖고, brute force(마구잡이/ 무차별 대입) """
    for x in range(2, num):
       if num % x == 0:
          return False
    return True

 

def finding_prime_sqrt(number):

    """ 제곱근 이용 """
    num = abs(number)
    if num < 4 : return True
    for x in range(2, int(math.sqrt(num)) + 1):
       if number % x ==0:
          return False
    return True

 

def finding_prime_fermat(number):

    """ 페르마 소정리 이용 """
    if number <= 102:
        for a in range(2, number):
            if pow(a, number -1, number) != 1:
                return False
        return True
   else:
       for i in range(100):
           a = random.randint(2, number -1)
           if pow(a, number - 1, number) != 1:
              return False
       return True

 

def test_finding_prime():
     number1 = 17
     number2 = 20
     assert(finding_prime(number1) is True)
     assert(finding_prime(number2) is False)
     assert(finding_prime_sqrt(number1) is True)
     assert(finding_prime_sqrt(number2) is False)
     assert(finding_prime_fermat(number1) is True)
     assert(finding_prime_fermat(number2) is False)
     print("테스트 통과!")

 

if __name__ == "__main__":
     test_finding_prime()

 

 

 

 

 

 

출처: 파이썬 자료구조와 알고리즘, 미아 스타인 지음 최길우 옮김