[프로그래머스 / Python] 소수 찾기(1단계) | 초코더

문제 설명

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

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

(1은 소수가 아닙니다.)

 

제한 사항

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

 

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

입출력 예 #1

1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2

1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

​

접근법

첫번째 방법

처음에는 1부터 숫자 n까지의 수들을 각각 정수들로 나누었을때 나누어떨어지지 않는 경우에 소수로 세어주려 했습니다. 하지만 그렇게 코드를 짰을경우 이중for문 때문인지 효율성 측면에서 점수를 받지 못하고 시간초과가 났습니다.

 

새로운 방법

에라토스테네스의 체를 이용하였습니다.

​

에라토스테네스의 체 링크 참조

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

잘못된 코드(시간 초과) 

def solution(n):
    s = 0
    sum = 0
    for i in range(2,n+1): #1부터 입력받은 숫자n사이에 정수중에서
        for j in range(2,i): #각각의 정수를 정수보다 작은수들로 나누었을때
            if i%j == 0: #나누어떨어지면
                s += 1 #s를 증가시키고
        if s == 0: #s가 0개이면 소수로 간주해서
            sum += 1 #sum을 증가
        s = 0 #s는 다시 초기화
    return sum 

 

나의 코드

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