소수 찾기

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

프로그래머스

문제풀이

기사 단원 문제와 마찬가지로 에라스토테네스의 체 알고리즘을 응용했다. lv.1 이기 때문에 제곱근 이하의 범위에서만 확인해도 통과가 가능하다만 주어진 시간이 10초고 n이 100만이 아닌 1억까지 주어졌을때 제곱근을 이용한 방법만으로는 시간 초과가 날것이다. 

def solution(n):
    answer = 0

    # 1은 소수가 아니라 0 반환
    if n < 2:
        return answer

    primes = [True] * (n + 1)
    primes[0] = primes[1] = False  # 0, 1은 소수가 아니므로 제거

    # 제곱근 이하의 범위에서만 확인
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False  # i의 배수들을 소수에서 제외

    # 소수의 개수 반환
    answer = sum(primes)
    return answer