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

1. 문제

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

2. 풀이 방법

에라토스테네스의 체

• 문제를 풀기 위한 개념은 에라토스테네스의 체입니다. 위키백과에서 관련 개념을 확인하실 수 있습니다.
• 소수인지 확인하기 위한 배열을 생성합니다. 배열의 크기는 n의 최대 숫자인 1000000로 합니다.
• 2부터 1000000의 제곱근인 1000까지 순차적으로 각 수의 배수를 소수 배열에서 0으로 표기합니다.(소수가 아니라고 판정합니다.)
• 2~1000 까지의 배수를 소수 배열에서 전부 제거한 후에, 주어진 n까지의 소수를 확인하여 답을 제출합니다.

3. 소스코드

3.1. 내 풀이

def solution(n):
    is_sosu_arr = [1] * (1000000 + 1)
    is_sosu_arr[0] = is_sosu_arr[1] = 0
    
    for i in range(2, 1001):
        if is_sosu_arr[i] == 0:
            continue
        k = 2
        while k * i <= 1000000: 
            is_sosu_arr[k * i] = 0
            k += 1
    
    answer = 0
    for i in range(2, n+1):
        if is_sosu_arr[i] == 1:
            answer += 1
            
    return answer

출처

• 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