[프로그래머스] 연습 문제 - 소수 찾기

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

 

 

2. 풀이

해당 수가 소수인지 아닌지를 판별하기 위해서는 해당 수의 제곱근까지만 확인해보면 된다는 점을 이용하여 코드를 작성하였다.

 

소수를 판별하는 is_prime 함수를 별도로 작성해서 True면 소수이니 answer list에 해당 수를 넣어주고, False면 소수가 아니니 다음 반복으로 넘어가는 식으로 코드를 작성했다. 

 

해당 문제 상에서 answer이 원래 int형으로 주어지는데 (초기 값이 answer = 0으로 주어짐) 코드 실행 시 넣은 소수들을 print해서 확인해보기 위해 list로 바꿨다. 

 

3. 초기 작성 코드 (성공)

def is_prime(num):
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
        
    return True

def solution(n):
    answer = []
    
    for i in range(2, n+1):
        if is_prime(i):
            answer.append(i)
            
    return len(answer)

 

소수 판별은 워낙 많이 나오는 문제고 간단해서.. 통과는 했는데요.

정확성 테스트 11번이랑 효율성 테스트 1-4 수행시간이 충격적이라서 다른 분들이 작성한 코드를 확인해보니,

'에라토스테네스의 체' 알고리즘을 활용해서 풀면 시간 복잡도 측면에서 훨씬 좋다고 해서 해당 알고리즘을 찾아보았습니다. 

 

4. 관련 알고리즘

에라토스테네스의 체

에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 알고리즘 중 하나로, 시간 복잡도가 O(NloglogN)으로 선형 시간에 동작할 정도로 빠르다고 합니다.

 

일반적으로 N의 개수가 적고 효율성을 따지지 않는 소수 판별 문제의 경우 3번에서 작성한 코드처럼 풀이해도 무관하나, N의 범위가 100만 이하의 문제에서 효율성 점수가 중요한 소수 판별 문제의 경우 에라토스테네스의 체 알고리즘이 유용하다고 하네요! (N이 100만을 넘어가기 시작하면 N 크기만큼의 리스트를 할당해야하므로 메모리 크기 측면에서 사용하기 쉽지 않음)

 

알고리즘

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

# 에라토스테네스의 체 알고리즘 구현

import math

n = 1000
array = [True for i in range(n+1)] # 처음엔 모든 수를 True로 초기화(0과 1은 제외)

for i in range(2, int(math.sqrt(n))+1):
	if array[i] == True: # i가 소수인 경우(남은 수인 경우)
    	# i를 제외한 i의 모든 배수를 False로 설정
        j = 2
        while i*j <= n:
            array[i*j] = False
            j+=1

 

5. 개선된 코드 - 에라토스테네스의 체 알고리즘 활용 (성공)

def solution(n):
    answer = [True for i in range(n+1)]
    
    for i in range(2, int(n ** 0.5)+1):
        if answer[i] == True:
            j = 2
            while i*j <= n:
                answer[i*j] = False
                j+=1
                
    answer[0] = False
    answer[1] = False
    
    return answer.count(True)

 

와~ 3000ms씩 걸리던 게 250ms 언저리로 개선되었다!