Daily Algorithm - Day 6

What is the 10001st prime number?

10001번째 소수를 구하는 문제이다.
우선 소수인지 구별해주는 함수를 구현한 후에 사용할 수 있는 2가지 방법이 떠오른다.

• 소수일 경우 배열에 추가해서 길이가 10001이 될때까지 구별하는 방법.
• 소수일 경우 변수 count를 1씩 늘려서 count가 10001이 될때까지 구별하는 방법.

시간복잡도는 별 차이가 없을 것으로 예상되니 기왕이면 배열을 이용해서 추후에 재활용이 가능하게 만들자

//Python

# 소수인지 확인해주는 함수
def isPrime (n):
    if n <= 1: 
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
    
# n번째 소수를 구하는 함수
def nth_prime (n):
    i = 1
    arr = []
    while len(arr) < n:
        i += 1
        if isPrime(i):
            arr.append(i)
    return i
    
 print(nth_prime(10001))
 
 >>> 104743

답은 잘 구해졌으나, 처리에 약 28초가 소모되었다. 더 빠르게 처리하기 위해 Day 2에서 참고했던 약수의 성질을 활용해 isPrime을 고쳐보자.

def isPrime (n):
	i = 2
	if n <= 1: 
		return False
	while i <= n**0.5:   # n의 제곱근보다 작은 약수가 1 밖에 없다면 n은 소수다.
		if n % i == 0: 
        	return False   
		i = i + 1
	return True

처리 속도를 확인하기 위해 time 모듈도 추가하였고, 최종적으로 나온 코드는 다음과 같다.

from time import time

# 약수의 성질을 이용해 소수인지 확인하는 함수.
def isPrime(n):
	i = 2
	if n <= 1: 
		return False
	while i <= n**0.5:
		if n % i == 0: 
			return False
		i = i + 1
	return True

# n번째 소수를 구하는 함수
def nth_prime (n):
    i = 1
    arr = []
    while len(arr) < n:
        i += 1
        if isPrime(i):
            arr.append(i)
    return i

start = time()
answer = nth_prime(10001)
end = time()

print(f"{answer}, {round(end - start, 5)}sec")

>>> "104743, 0.63682sec"

0.6초 정도면 만족스러운 결과다.

오늘은 여기까지.

-2024.12.26-