Algorithm : Programmers - 소수찾기

링크텍스트

👉 문제

🤔 생각해보기

1. 소수를 구하려면?
2. 갯수를 세려면?
3. 에라토스테네스의 체
   링크텍스트

👉 해답

def solution(n):
    
    sieve = [True] * (n+1)

    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:          
            for j in range(i+i, n+1, i):
                sieve[j] = False


    return len([i for i in range(2, n+1) if sieve[i] == True])

소수찾기를 할 때 최적의 로직은 에라토스테네스의 체를 사용하는것 같다.
까먹지 않도록 하자.