우선 리스트에서 x in list나 list.remove(x)는 O(n)의 시간 복잡도를 갖습니다.

따라서 에라토스테네스의 체를 구현할 때, 원소를 지운다는 것을 실제로 원소를 리스트에서 삭제하는 방식 대신 다른 방법으로 구현해야 할 것입니다. 대표적인 방법으로는 0과 1, 혹은 False와 True 등을 통해 체에서 걸러진 원소와 걸러지지 않은 원소를 나누는 방법이 있겠습니다.

이런 방법으로도 한번 해봤는데,

역시 시간복잡도에서 걸리는거 같습니다

조언 정말 감사드립니다!

결론부터 말씀드리면 prime이라는 별도의 집합을 만들 필요가 없습니다.

최종 출력에서 i*j의 값을 지우기 위해 따로 집합을 만들어 저장해두신 다음, 마지막에 한번에 제거하신 것으로 보입니다. 그러나 계산 과정에서 이 값을 지우는 방법이 존재합니다. 편의상 수의 범위를 1부터 n까지로 잡겠습니다.

1. 우선 1로만 채워진 길이 n+1짜리 리스트를 생성합니다. 이는 인덱스 번호가 실제 수를 의미하도록 하기 위함입니다 (l[0], l[1], ..., l[n]).

2. 2부터 floor(sqrt(n))까지 에라토스테네스의 체 알고리즘을 수행합니다. 지울 원소는 0으로 변경합니다. (l[i*j] = 0)

3. 완성된 리스트에서 1의 위치가 곧 소수 각각을 의미하게 됩니다.

개인적으로 자주 참고하는 사이트 링크입니다. 자세한 구현에 도움이 필요하시다면 참고하셔도 좋을 것 같습니다. 저 사이트에는 True/False로 값을 저장하는 코드가 작성되어 있는데, 사실 Python 내부적으로 True/False는 1/0에 대응되므로 크게 다를 건 없습니다.

정말 감사드립니다.

대댓글 기능이 없어서 여기에 글을 씁니다.

코딩 초보로서 여기저기 알아보면서 공부하는데,

생각보다 제 궁금증을 해결하기가 어렵더군요.

정말 진심으로 감사드리옵고, 항상 행복이 가득하시길 바랍니다.