[알고리즘] 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 소수의 판별

[알고리즘] 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 소수의 판별

• 소수: 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나우어떨어지지 않는 자연수
  • 6은 1, 2, 3, 6으로 나누어 떨어지기 때문에 소수가 아니다.
  • 7은 1과 7을 제외하고는 나누어떨어지지 않기 때문에 소수이다.
  • 소수는 2보다 큰 자연수에 대하여 정의되므로, 1은 소수에 해당하지 않는다.

---

• 어떠한 수 X가 주어졌을 때 해당 수가 소수인지 아닌지 판별하는 방법

  • 가장 간단한 방법은 X를 2부터 X-1 까지의 모든 수로 나누어보는 것. 만일 2부터 X-1 까지의 모든 자연수로 나누었을 때 나누어떨어지는 수가 하나라도 잇다면 X는 소수가 아니다.

  • 소수 판별 소스코드 예제 - 시간복잡도: O(X)

    def is_prime_number(x):
        for i in range(2, x):
            if x % i == 0:
                return False
        return True
    
    print(is_prime_number(6))

  • 개선된 소수 판별 소스코드 예제 - 시간복잡도: O(X^(1/2))

    import math
    
    def is_prime_number(x):
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        return True

    16이라는 수의 약수는 1, 2, 4, 8, 16이다. 가운데 약수 4를 기준으로 하여 대칭적으로 2개씩 앞뒤로 묶어서 곱하면 16을 만들 수 있다.

    • 1 X 16 = 16
    • 2 X 8 = 16
    • 4 X 4 = 16
    • 8 X 2 = 16
    • 16 X 1 = 16

    여기서 알 수 있는 점은 가운데 약수를 기준으로 해서 각 등식이 대칭적인 형태를 보인다는 것이다. 따라서 우리는 특정한 자연수 X가 소수인지 확인하기 위하여 바로 가운데 약수까지만 나누어떨어지는지 확인하면 된다. 다시 말해 제곱근까지만(가운데 약수까지만) 확인하면 된다.