챌린저스 매일 인증 (4) 소수 찾기

❓문제

🤔 과정

• 총 3번의 시도
• (1) 이중 for문을 사용해 소수를 구했다.
• -> 3개의 예제에서 시간초과가 나고 효율성 테스트에서 계속 떨어짐
• (2) 2를 제외하고 홀수만 시도 (시간 감소를 위해)
• -> 같은 이유로 실패
• (3) 소수 구하기에서 시간복잡도가 루트 n으로 가장 적게드는 isPrime 함수를 따로 만들어 시도
• -> 같은 이유로 실패

이쯤 되니 이중 for문을 쓰면 안된다는 생각이 들었다.

그렇게 검색을 해서 발견한 개념

❗️에라토스테네스의 체

아마 에라토스테네스의 체로 효율성까지 챙기길 바랬던 것 같다.

🙋🏻‍♀️ 내 코드

def solution(n):
    answer = set(range(2, n+1))

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