parispoly137   5년 전

진짜 4일 째 10시간 이상 오류 있는지 계속 돌려보고 생각해봤습니다.

답은 잘 나오는데 시간초과가 계속 뜹니다.

해결 방법 조언 부탁드립니다!!

khj94811   5년 전

에라토스테네스의 체의 시간 복잡도는 O(NloglogN)입니다. 그렇다면 T개의 테스트케이스(T<=100,000)에 대해서 계속해서 에라토스테네스의 체를 돌리는 것은 시간초과가 당연히 발생할 수 밖에 없습니다.

그렇다면, 에라토스테네스의 체를 이용해서 미리 임의의 소수들을 전처리 해둔다면 어떻게될까요??

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