[프로그래머스] 소수찾기

프로그래머스 - 연습 문제

Review

• 계속 시간초과 나오다 에라토스테네스의 체로 겨우 통과
• 1차 시도: 1과 자기 자신으로 나누어지는 수만 카운트하자 -> 시간 초과
• 2차 시도: 일단 2로 나눌 수 있는 수는 거르고 시작하자. 그리고 어차피 자기 자신/2 이상으로 나눌 수는 없으니까 최대한 반복 횟수 줄여보자 -> 시간 초과
• 3차 시도: 질문하기 피드 보니 에라토스테네스의 체를 사용하라고 한다 -> 통과
• 예전이랑 지금이랑 시간 제한이 달라진 것 같음.
• python의 set()을 사용하면 더 짧고 간단하게 구현 가능하다.

Code (Python)

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

    for i in range(2, m + 1):
        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])