CodingTest) 소수(Prime Number) 판별

소수 (Prime Number)

• 소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 자연수이다.
• 4는 1, 2, 4 를 약수로 가지므로 소수가 아니다
• 7은 1, 7 을 약수로 가지므로 소수이다.

소수 판별 기본적인 알고리즘 (Python)

def is_prime_number(n):
    if n == 1:
        return False
    for x in range(2, n):
        if n % x == 0:
            return False
    return True

print(is_prime_number(6))
print(is_prime_number(11))

실행 결과

False
True

위 함수의 경우 2부터 X-1 까지의 모든 자연수에 대하여 연산을 수행.

• 시간 복잡도는 O(n) 이다.

모든 약수는 중앙을 기준으로 짝을 지어 이루는 것을 알 수 있다.

• 8의 경우 1, 2, 4, 8의 약수를 가진다.
• 1 X 8 = 8 과 8 X 1 = 8 이 대칭이고, 2 X 4 = 8 과 4 X 2 = 8 은 대칭이다.

이에 따라 2부터 n-1 까지의 모든 자연수에 대하여 연산을 수행하지 않고, n^(1/2) 즉, n의 제곱근 까지의 모든 자연수에 대하여 연산을 수행한다.

개선된 소수 판별 알고리즘 (Python)

def is_prime_number(n):
    if n == 1:
        return False
    for x in range(2, int(n**(1/2)) + 1):
        if n % x == 0:
            return False
    return True

print(is_prime_number(4))
print(is_prime_number(11))

실행 결과

False
True

위 함수의 경우 2부터 n^(1/2) + 1 까지의 자연수에 대하여 연산을 수행

• 시간 복잡도는 O(n^(1/2)) 이다.