소수 찾기 (lv1)

 지금까지 소수를 찾는 문제는 제곱근까지 나눠보는 방법을 사용했다. 그러나 에라토스테네스의 체 라는 약 10배정도 빠른 알고리즘이 존재한다는 사실을 알아냈다.

에라토스테네스의 체 - 나무위키 (namu.wiki)

에라토스테네스의 체 - 나무위키

---

코드

my

def solution(n):
    answer = 0
    for v in range(2,n+1):
        for divisor in range(2, int(v**0.5)+1):
            if v % divisor == 0:
                break
        else :
            answer += 1
    return answer

에라토스테네스의 체

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

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    for i in range(2, int(n ** 0.5) + 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])