프로그래머스 [Lv. 1] 소수 찾기 {언어 : Python}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12921?language=python3

프로그래머스

정답 코드

def solution(n):
    if n < 2:
        return 0
    
    sieve = [True] * (n + 1)  # 소수 여부를 저장할 배열
    sieve[0] = sieve[1] = False  # 0과 1은 소수가 아니므로 False
    
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:  # i가 소수라면
            for j in range(i * i, n + 1, i):  # i의 배수를 모두 False로 처리
                sieve[j] = False
    
    return sum(sieve)  # True로 남아 있는 값들의 개수를 세면 소수의 개수

풀이 방법

1. sieve 리스트 초기화:
   • 처음에 모든 숫자를 소수로 가정하고 True로 초기화한다.
   • 0과 1은 소수가 아니므로 False로 설정한다.
2. 소수 판별 및 배수 제거:
   • 2부터 시작해서 소수로 판별된 숫자의 배수를 False로 설정한다.
   • 이 과정을 숫자의 제곱근까지 반복한다.
3. 결과 반환:
   • 소수로 남아 있는 숫자들의 개수를 반환한다.

느낀점

• 에라스토테네스의 체...