yjkim9591   6달 전

먼저 에라스토테네스의 체를 통해 1000000까지의 소수를 구하고, 낮은 소수부터 1개씩 정하고 그보다 크거나 같은 소수와의 합이 n이 되도록 판별하도록 만들었습니다.

문제의 조건대로 하면 999999번째에 0을 입력하고, 그동안은 1000000에 가꺄운 짝수를 계속 입력하여도 시간복잡도가 낮아야 한다는 소리인데, 이게 가능한지 모르겠습니다. 일단 1000000까지의 소수를 구하는 곳에서만 해도 이미 1초를 넘을 것 같습니다. 에라스토테네스의 체를 쓰려면 예를 들어 1000000까지의 소수를 구하려면 for문을 총 1000000번 반복해야 하는 것 아닌가요?

처음에는 malloc을 이용해서 해결하려했는데, 생각해보니 테스트케이스에서 위와 같이 입력한다면 1초 안에 실행되기는 힘들 것 같은데, 혹시 어떤 방법으로 시간을 줄일 수 있을까요?

bamgoesn   6달 전

에라토스테네스의 체를 사용해 소수를 전처리하는 과정에서, 바깥쪽 루프는 i*i<=n인 i에 대해서만 확인해도 충분합니다. 즉, int i=2; i*i<=n; i++이라 해도 충분합니다.

이렇게 해도 되는 이유는, sqrt(n)보다 큰 i에 대해서 i*j는 무조건 이전의 루프에서 이미 다 처리되었기 때문입니다.

추가로, i가 소수가 아니라면 이미 그 i를 나누는 소수에 대한 루프를 한 번 지났었고, 그 과정에서 i의 배수는 전부 소수가 아니라고 걸렀기 때문에, i가 소수인 경우는 j의 루프를 돌리지 않아도 됩니다.

이 두 가지를 적용했을 때 에라토스테네스의 체 시간복잡도는 O(nloglogn)이 되어, n=1e6에 대해 무리 없이 돌아갑니다.

yjkim9591   6달 전

선생님이 말한대로 코드를 다시 짰는대도 시간초과가 뜹니다. 혹시 시간복잡도를 줄일 수 있는 다른 방법은 없을까요?

bamgoesn   6달 전

제가 말한대로 짰다고만 말씀하시면 정확히 어떤 원인으로 시간 초과가 났을지 잘못 짚을 확률이 높습니다. 말씀드린 사항 외에도 시간 초과가 만한 다른 부분이 있었을 수도 있고, 제가 말씀드린 걸 잘못 적용하셨을 수도 있는 등 가능성이 너무 많습니다.

코드를 고치신 후에 질문을 이어나갈 땐 수정 후 코드를 다시 첨부해주세요.,

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