<프로그래머스 문제풀이: 소수 찾기> Level 1 - 파이썬

 

내가 싫어하는 소수 문제이다. 언제나 봐도 생각이 잘 안나기 때문에 매번 새롭게 머리를 굴려야 된다는 느낌이 있다. 우선 처음에 짠 풀이는 다음과 같다:

def solution(n):
    list_n1 = [x+1 for x in range(n)]
    list_n1.remove(1)
    list_n2 = sorted(list_n1, reverse=True)
    for i in list_n1:
        for j in list_n2:
            if i == j:
                continue
            elif j%i == 0:
                list_n2[list_n2.index(j)] = 0
    
                
    return len(list(set(list_n2)))-1

우선 list_n1을 1 부터 n까지의 리스트로 정의를 하고, 1을 제외시켜준다.

list_n2는 list_n1의 역순인 리스트로 정의해준다.

i 는 list_n1의 순서로, j 는 list_n2의 순서로 정의를 해주고 만약 j를 i로 나누었을 때 0으로 나온다면, list_n2에서 해당 값을 0으로 설정해준다.

마지막으로 list_n2를 set으로 통과시키고 이를 리스트로 만들어서 길이를 구하고, 이에 0이 포함되어 있으므로 1을 빼준다.

 

원리상 완벽해보이지만, 하나는 에러가 나고, 시간초과가 나는 테스트 값들이 여럿 있었다. 에러가 나는 값은 n 값이 2일때 인 것을 알아냈다. 이를 고치려면 너무 오랜 시간이 걸리고 힘들거라고 생각돼서 다른 사람의 풀이를 참조하기로 했다.

 

 

※ 다른 사람의 풀이

 

def solution(n):
	num = set(range(2, n+1))
	for i in range(2, n+1):
		if i in num:
			num -= set(range(2*i, n+1, i))
	return len(num)

 

에라토스테네스의 체를 사용하여 푼 방식이다. 프로그래머스 문제풀이에서 가장 많은 좋아요를 받은 풀이법이기도 하다. 소수를 구할 때 에라토스테네스의 체를 쓴다는 것은 알고 있었지만 미처 생각을 못한 것 같다. 우선 num에 2부터 n+1 까지의 range인 set를 저장시켜주고, i의 범위도 똑같이 설정시켜준다.

만약 i 가 num 에 있을 경우, i 보다 한 배수 큰 숫자부터 n+1까지의 범위를 공차가 i 가 되게끔 하여 set를 구성한 후, num에서 빼준다.

마지막에는 num의 길이를 돌려주면 된다.