에라토스테네스의 체를 사용해 소수를 전처리하는 과정에서, 바깥쪽 루프는 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 1년 전
먼저 에라스토테네스의 체를 통해 1000000까지의 소수를 구하고, 낮은 소수부터 1개씩 정하고 그보다 크거나 같은 소수와의 합이 n이 되도록 판별하도록 만들었습니다.
문제의 조건대로 하면 999999번째에 0을 입력하고, 그동안은 1000000에 가꺄운 짝수를 계속 입력하여도 시간복잡도가 낮아야 한다는 소리인데, 이게 가능한지 모르겠습니다. 일단 1000000까지의 소수를 구하는 곳에서만 해도 이미 1초를 넘을 것 같습니다. 에라스토테네스의 체를 쓰려면 예를 들어 1000000까지의 소수를 구하려면 for문을 총 1000000번 반복해야 하는 것 아닌가요?
처음에는 malloc을 이용해서 해결하려했는데, 생각해보니 테스트케이스에서 위와 같이 입력한다면 1초 안에 실행되기는 힘들 것 같은데, 혹시 어떤 방법으로 시간을 줄일 수 있을까요?