1-11 소수 나열하기 (에라토스테네스의 체)

Question

1. 현재 학습 진도 몇 챕터/몇 강을 수강 중이신가요? 1-11 2. 시도해보신 내용 def find_prime_list_under_number(number): if number <= 1: return [] is_prime = [True] * (number + 1) is_prime[0] = is_prime[1] = False # 0과 1은 소수가 아님 for i in range(2, int(number ** 0.5) + 1): # 2 ~ 루트(number)까지 if is_prime[i]: # i가 소수라면, i의 배수들은 모두 소수가 아님 for j in range(i*i, number + 1, i): is_prime[j] = False return [i for i, v in enumerate(is_prime) if v] 기존 풀이보다 에라토스테네스의 체 방식이 직관적인 거 같아서 개선해보았습니다. 기존 방식과 지금 방식 중 무엇이 더 효율적인가요?

딩코딩코 · Answer

안녕하세요 좋은 질문 감사합니다! 말씀주신대로 에라토스테네스의 체 방식이 강의에서 다룬 2차 개선 방식보다 더 효율적입니다! 강의의 2차 개선 방식은 각 숫자 n에 대해 기존에 찾은 소수 목록을 순회하면서 i * i > n 조건으로 조기 종료하는 방식입니다. 이 방식은 숫자마다 나눗셈 연산을 반복합니다. 반면 에라토스테네스의 체는 boolean 배열을 미리 만들어두고, 소수를 발견할 때마다 그 배수들을 한 번에 걸러냅니다. 시간복잡도가 O(N log log N)으로, 나눗셈 기반 방식보다 빠르고 메모리 접근 패턴도 단순합니다. 특히 범위가 클수록 차이가 더 크게 납니다. 작성하신 코드도 정확하게 구현되어 있습니다. i*i부터 시작해서 i 간격으로 배수를 제거하는 부분까지 올바르게 적용하신 것 같습니다!! 새로운 시도 넘 좋습니다 ㅎㅎㅎ 좋은 하루 되시길 바랍니다