jun2077681   5달 전

아무리 생각해도 시간초과를 해결할 방법이 안떠올라요...살려주세요 ㅠㅠ

dotorya   5달 전

x이하의 모든 소수를 계산하는 건 아마 위와 같이 짜면 시간이 매우 오래 걸릴 겁니다. (항상 이전의 모든 소수로 나누어지는지 검사하므로, 자세한 증명은 생략하지만 대략 O(x^2/lg x) 정도의 시간이 걸립니다.


더 좋은 방법은 에라토스테네스의 체를 사용하는 방법입니다. 이것의 시간복잡도는 약 O(x lglgx) 정도이므로, 문제에서 사용하기 충분할 겁니다. 에라토스테네스의 체를 이용해 다시 구현해 보시면 될 것 같네요.


(추가로, 이런 경우에 포인터를 사용해 linked list로 저장하는 것 역시 시간을 느리게 할 수 있습니다. std::vector나 배열을 사용하시는 것을 추천드립니다.)

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