[프로그래머스] 소수 찾기

* 문제

programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

* 문제 풀이 

- 첫째, n개의 prime_list를 미리 생성해둔다.

- 둘째, m은 n의 루트를 씌운 수로 m까지만 반복문을 실행시킨다.

- 셋째, for문을 이용해 2의 배수, 3의 배수를 제거한다.

- 넷째, 남은 수가 소수이다.

 

* 생각

- 이중 for문을 사용해 처음에 문제를 풀었는데 효율성 문제 때문에 풀리지 않았다.

- 에라토스테네스의 체 방법을 적용하니 효율성 문제를 통과했다.

- [위키피디아] : 에라토스테네스의 체 설명

 

* 코드 

def solution(n):
    n = n+1
    prime_list = [True] * n
    
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if prime_list[i] == True:
            for j in range(i+i, n, i):
                prime_list[j] = False
    
    prime_list = ([i for i in range(2, n) if prime_list[i] == True])
    answer = len(prime_list)
    return answer