[CodingTest/Python] 소수(Prime Number) 판별

소수란?

2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수

 

1. 2부터 n-1까지 모두 확인해보기

def is_prime_number(x):
	# 2부터 (x-1)까지의 모든 수를 확인
    for i in range(2, x):
    	# x가 해당 수로 나누어 떨어지면
        if x % i == 0:
        	return False
    # 나누어 떨어지는 경우가 없으면
    return True

시간복잡도 : O(x) → x의 크기가 크면 비효율적

 

2. 2부터 제곱근까지만 확인해보기

예) 16의 약수 : [1, 2, 4, 8, 16]

해당 수를 살펴보면 가운데 수를 기준으로 대칭적으로 곱을 통해 16을 만들 수 있다. 이를 통해, 소수의 절반에 해당하는 제곱근까지만 살펴보면 소수 판별이 가능하다는 것을 알 수 있다. 

import math

def is_prime_number(x):
	# 2부터 x의 제곱근까지의 모든 수를 확인
    for i in range(2, int(math.sqrt(x))+1):
    	# x가 해당 수로 나누어 떨어지면
        if x % i == 0:
        	return False
    # 나누어 떨어지는 경우가 없으면
    return True

math 라이브러리를 사용하지 않고 다음과 같이 사용할 수 있음을 알아두자.

def is_prime_number(x):
	# 2부터 x의 제곱근까지의 모든 수를 확인
    for i in range(2, int(x**0.5)+1):
    	# x가 해당 수로 나누어 떨어지면
        if x % i == 0:
        	return False
    # 나누어 떨어지는 경우가 없으면
    return True

시간복잡도 : O(x^(1/2))

 

3. 에라토스테네스의 체

에라토스테네스의 체를 이용한 방법의 경우 범위 내의 모든 수에 대해 소수를 판별하게된다. 

 

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다 )
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

import math

def is_prime_numebr(x):
    # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
    array = [True for i in range(n+1)] 
    
    # 에라토스테네스의 체
    # 2부터 n의 제곱근까지의 모든 수를 확인
    for i in range(2, int(math.sqrt(n))+1): 
    	# i가 소수인 경우(남은 수인 경우)
        if array[i] == True:
        	# i를 제외한 i의 모든 배수를 제거
            j = 2
            while i * j <= n:
            	array[i * j] = False
                j += 1
    
    # 2부터 n까지의 모든 수에 대하여 소수 판별
    return [i for i in range(2, n+1) if array[i]]

시간복잡도 : O(xloglogx) → but x크기 만큼의 메모리가 필요

 

Ref.

알라딘: 이것이 취업을 위한 코딩 테스트다 with 파이썬 (aladin.co.kr)