두 코드에서 if (tmp[i]) continue;의 의미가 달라지니 더 오래걸리는 게 자연스럽겠네요

댓글 감사합니다.

죄송하지만 의미가 달라진다는 부분에서 잘 이해가 가질 않습니다. 혹시 추가적인 설명을 부탁드려도 될까요?

------------------------------------------------------------

M: 50, N: 100이라고 가정했을 때

1. for (int j = M; j <= N; j++)의 경우

i는 2일때부터 sqrt(N)까지

50 % 2

50 % 2

...

100 % 2

50 % 3

51 % 3

...

2. for (int j = 2; j <= N; j++)

i는 2부터 sqrt(N)까지

2 % 2

3 % 2

...

100 % 2

2 % 3

3 % 3

...

이렇게 체크하게 되는데 결국 j = 2부터 시작하는게 더 많은 양을 체크하게 되는 게 아닌가요?

j <= M에 대해서만 소수 판정을 한다는 것은 소수로만 나눠보면 된다는 점은 간과하겠다는 것과 같습니다.

N = 1e6, M = 1e3인 예시를 봅시다. M ~= sqrt(N)인 예시를 골랐습니다.

i = 4는 소수가 아닙니다. 2번 코드의 경우 tmp[i] == 1일 것이기에 아래 포문을 스킵합니다. 1번 코드는 그렇지 않습니다.

결국 i <= 1e3까지 체크하는 (i, j)의 대략적인 개수는 

1번 코드의 경우 sqrt(N) * (N-M), 2번의 경우 sqrt(N)/log(sqrt(N)) * N개가 되겠네요.  (소수 정리에 따르면 X 이하의 소수의 개수가 X / log(X)쯤 됩니다.)

log(1000) = 6.91이니 7배까지도 차이가 날 수 있다는 계산이 됩니다.

위 예측에 비해 서버 제출 시의 차이가 적은 편이라 의아함이 있어

1000 1000000

으로 직접 돌려봤습니다.

코드 1은 0.297~0.340s, 코드 2는 1.78s~1.85s 

실제로는 1000까지 168개의 소수가 있어서 6배 차이는 위 계산이 정확하다는 것을 보여주고, 채점 데이터에는 위 케이스가 없는 것 같네요.

이렇게 직접테스트까지해주시고 시간을 내주어 알려주셔서 감사합니다. 

덕분에 어디서 차이가 나는지 확실히 이해했습니다!!

log부분에서 멘붕하긴 했지만 수학공부도 할 수 있게되어 좋은 시간이 되었습니다.

좀 더 분발해서 log부분 설명을 이해하도록 노력하겠습니다.

새해복 많이 받으시고 코로나 조심하세요! :)