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

---

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

제한사항

• n은 2이상 1000000이하의 자연수입니다.
• 문제 보러가기

문제 풀이

(1) 코드 작성

import numpy as np

def solution(n):
    l = []
    for i in range(2, n+1):
        prime = True
        for j in range(2, int(np.sqrt(i))+1):
            if i % j == 0:
                prime = False
                break
        if prime:
            l.append(i)
    return len(l)

(2) 코드 리뷰

위에 내가 작성한 코드는 효율성 측면에서 좋지 않은 코드이다. 테스트에서 시간이 초과되기 직전에 성공한 케이스이다. 제한조건을 보면 n이 1000000 이하의 값을 가진다는 점과 반복문을 사용했다는 점에서 효율성이 매우 떨어진 것으로 보인다. 그래서 다른 사람이 작성한 코드를 보고 해결 방법을 추가하였다.

🔍 다른 사람 코드 리뷰

def solution(n):
    num = set(range(2, n+1))
    for i in range(2, n+1):
        if i in num:
            num -= set(range(2*i, n+1, i))
    return len(num)

다른 사람이 작성한 코드를 보면 set으로 2부터 n까지의 숫자를 담고 반복문을 통해 2~n 사이의 값이 num이라는 컨테이너 안에 존재할 때 n의 배수를 빼주는 방식으로 접근했다(차집합). set은 차집합, 합집합, 교집합 기능을 한다. 이 점을 이용해서 문제에 접근한 것으로 보인다. 이렇게 하면 전체 범위에 접근하는 것이 아니라 특정 값의 배수를 빼주는 과정이 추가되기 때문에 2~n 사이의 모든 값에 접근하지 않아도 된다. 즉, 시간 절약을 할 수 있다. 실행 결과를 보았을 때 효율성 테스트 부분에선 이전 코드(내가 작성한 것)와 약 10배 이상 차이가 났다. 앞으로 반복문을 사용할 때 list만 사용하는 것이 아닌 set을 이용할 수 있는 부분이 있다면 set을 사용해 보는 연습을 해보아야겠다.

👩🏻‍💻개인 공부 기록용 블로그입니다
오류나 틀린 부분이 있을 경우 댓글 혹은 메일로 따끔하게 지적해주시면 감사하겠습니다.