[프로그래머스] 소수 찾기Lv.1 - Python

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

나의 풀이

def solution(n):
    a = [0] * (n + 1)
    for i in range(2, len(a)):
        for j in range(2, len(a)):
            idx = i * j
            if idx > n:
                break
            a[idx] = 1
    return a[2:].count(0)

• 처음 그냥 이중 for문을 이용하면 답은 맞지만, 시간 효율성 측면에서 실패하게된다.
• 에라토스테너스의 체를 사용한다.
• 에라토스테너스의 체는 소수의 배수는 소수가 아니라는 규칙이다.
• 우선 값이 0인 배열을 입력값 + 1 만큼 사이즈로 만들어준다.
• 배열은 인덱스를 0부터 세기 때문에, 인덱스 10을 사용하기 위해서는 하나 더 큰 11사이즈로 만들어 줘야 하기 때문이다.
• 그리고 반복문을 돌린다.
• 2부터 시작해서 n + 1 까지 각 수의 1의 배수를 제외한 배수의 인덱스의 값을 1로 바꿔준다.
• 배수가 입력값을 넘어가면 반복을 종료한다.
• 그렇게 하면 각 수의 배수의 인덱스는 1이되고 소수 인덱스의 값은 0이 남게 된다.
• 배열의 인덱스 2부터 값이 0인 갯수를 반환하면 된다.

느낀점

예전에 자바로 풀었었는데, 그 사이에 에라토스테너스의 체를 까먹어버렸다.