chsun0303   1년 전

시간초과가 나서 질문한 내역들을 쭉 보다가
에라토스테네스체를 사용해 보라는 다른 댓글들을 봤습니다.
그런데도 시간초과가 나는데 어떻게 해야할지 궁금합니다.
감사합니다.

djm03178   1년 전

파이썬에서 list를 내부적으로 배열로 관리하기 때문에 원소를 제거하는 연산은 뒤의 원소들을 하나씩 다 끌어오는 O(n) 시간이 걸린다고 알고 있습니다. 특히 0번째 원소를 제거하는 것은 전체 원소의 수만큼의 시간을 고스란히 소비할 것 같네요.

에라토스테네스의 체는 플래그를 통해서 관리하면 효율적으로 만들 수 있습니다.

djm03178   1년 전

참고로, M 이상 N 이하의 소수를 구해야 하는데 이 코드는 M 이상 N 미만의 소수를 구하고 있습니다.

댓글을 작성하려면 로그인해야 합니다.