[소수의 판별] 프로그래머스 L1 '소수 찾기' (Python)

<문제 링크>

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

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

---

<문제 풀이>

1. 에라토스테네스의 체 공식으로 소수 구하기

 

<코드>

def solution(n):
    answer = 0
    
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * (n+1)

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n+1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return len([i for i in range(2, n+1) if sieve[i] == True])

 

<고쳐야 할 점>

• 소수 찾는 공식 외우기
• 복습 알고리즘