[코딩 문제 풀이(파이썬/Python)] 프로그래머스 _ 소수 찾기

[문제 설명]

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

[제한 조건]

n은 2이상 1000000이하의 자연수입니다.

 

다음의 두 코드는 틀린 것은 아니지만, 효율성 문제로 통과되지 않는다.

# 효율성 탈락 (1)
def solution(n):
    answer = [2,3]
    for x in range(4,n+1): 
        cnt = 1
        for i in range(2, int(x**(0.5)+1)):
            cnt = cnt * (x%i)
        if cnt !=0:
            answer.append(x)
    return answer
    
# 효율성 탈락 (2)
def solution(n):
answer = [x for x in range(2,n+1) if 0 not in ([x%i for i in range(2, x)])]
return answer

소수임을 확인하는데 있어, 루트 n보다 작은 소수들로 나누어 떨어지는지만 확인하면 됨은 동일하다.

def solution(n):
    prime = []
    if n == 1:
        pass
    else:
        for i in range(2, n+1):
            cnt = 0
            for n in range(2,int(i**(0.5)+1)):
                if i%n ==0:
                    cnt +=1
                    break
            if cnt ==0:
                prime.append(i)
    return(len(prime))

1이 들어가도 함수가 성립해야 해서 좀 억지스러움이 있다. 소수가 아니면 언제라도 for문에서 break 하도록 해 효율성 테스트를 통과했다. 그렇게까지 좋은 방법은 아니다.

 

'에라토스테네스의 체'를 이용한 아래의 코드가 빠른 방법인 것 같다. 가장 작은 소수인 2의 배수부터 지워나가면서, 그 다음 제일 작은 소수는 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)

2부터 n까지 모든 자연수가 있는 집합에서, 자신을 제외한 2,3,5,7,11, ... 의 배수들을 차례로 제거해나가는 코드다. test case에서 내가 작성했던 코드와 비교해 속도 면에서는 10배 가량 차이나기도 한다.