소수 찾기 (Programmers 12921)

🧑‍💻 문제

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

제한 사항

• n은 2이상 1000000이하의 자연수입니다.

n	result
10	4
5	3

🧑‍💻 해결방법

• 에라토스테네스의 체로 접근하기 (효율성)
• 리스트로 생성한 후 직접적으로 빼주기

🧑‍💻 코드

def solution(n):
    arr = set(range(2, n + 1))
    for i in range(2, n + 1) :
        if i in arr :
            # 2의 배수부터 i의 배수까지 리스트에서 모조리 제거해준다.
            arr -= set(range(2 * i, n + 1, i))
    return len(arr)

🧑‍💻 총평

• 이전에 풀었던 에라토스테네스의 체를 활용해서 풀어야하는데 C에서 python으로 어떻게 가져오느냐에 대한 고민이있었다.
• 이번에도 보다 파이썬스럽게 풀었는데 n까지의 수를 나열한 리스트를 set으로 생성한 뒤에 추후에 2의 배수부터 i의 배수까지 리스트 내에서 모조리 제거한 후에 길이를 리턴해주는 방법이다.
• 풀었던 소수 문제(에라토스테네스의 체)에서 버벅인 것을 보아 아직 연습량이 많이 부족했다는 것을 느낄 수 있었다.