dlsfuf227   2년 전

답은 분명 맞게 나오는데 시간초과가 걸리는 이유가 궁금합니다.

또 어떻게 하면 시간초과를 극복할 수 있을까요?

runnie0427   2년 전

우선 python이라면 input이 몇개인지를 확인하기 힘든 경우에는 안전을 위해(?)서 빠른 입출력(sys.stdin.readline)을 사용하시는 걸 권장해요.

그리고 매번 n이 들어올 때마다 소수 개수를 처리하고 있는데, 그것보다는 범위가 123456까지 들어온다고 정해져 있으니, 처음부터 123456*2까지의 소수여부를 모두 체크한 뒤에 돌리면 조금 더 빠를 거예요.

조금 더 좋은 팁을 드리자면, n부터 2n까지의 소수 개수를 n개의 루프를 돌면서 체크하기 보다는, 1에서 n까지의 소수가 몇개인지를 체크해두면 더욱 빠르게 해결할 수 있습니다!

ysh9718   2년 전

1에서 n까지의 소수 개수가 n부터 2n 까지 소수 개수랑 같다는 말인가요?

runnie0427   2년 전

앗 그건 아니고, 적당한 크기의(제한 조건*2만큼의)모든 자연수 n에 대해서1부터 n까지의 소수가 몇개 있는지를 각각 구해두면, n부터 2n까지의 소수 개수는 (1부터 2n까지의 소수 개수)-(1부터 n-1까지의 소수 개수)로 구할 수 있습니다!

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