이 방법으로 지울 때, 2번 과정에서 찾은 P들이 소수입니다. 지운다는 건 그냥 지운 것 뿐이고 과정 자체는 에라토스테네스의 체 그 자체입니다.

어.. 아직 이해가 안가는데요 ㅠ 2나 3 같은 것을 지우면 결과도 달라지는 것 아닌가요..?

2번 과정에서 찾은 수들이 소수이고, 3번 과정에서 지운 수들은 P 외에는 소수가 아닙니다.

이 과정을 똑같이 수행하되, 다른 배열을 하나 만들어서 2번 과정에서 찾은 수들만 그쪽에 넣어주는 코드를 추가한다면 알고 계신 에라토스테네스의 체와 같은 결과를 얻게 됩니다.

이 문제에선 2번과정에서 찾아낸 소수들도 3번에서 별도로 저장하지를 않고 그냥 지워버리기 때문에 그렇게 느끼신 듯 합니다.

이 문제에서 "지운다"는 게 "소수가 아니라고 판정했다"는 뜻이 아닙니다. 다시 말씀드리지만, 지운 건 그냥 지운 거고, 그 이전에 2번에서 찾은 P들은 소수가 맞습니다.

예를 들어, N=10이라고 하고 이 과정을 따라가보면,

처음에 2 3 4 5 6 7 8 9 10 의 수를 적습니다.

지워지지 않은 수 중 가장 작은 수는 2입니다. 따라서 2는 소수입니다. 이제 2를 비롯해서 2의 배수들을 모두 지웁니다.

3 5 7 9가 남았습니다. 다시 지워지지 않은 수 중 가장 작은 수는 3입니다. 따라서 3도 소수입니다. 이제 3을 비롯해서 3의 배수들을 모두 지웁니다.

5 7이 남습니다. 5가 제일 작으므로 5도 소수입니다. 5의 배수를 모두 지우면 7이 남고, 7도 소수가 됩니다.

보통 에라토스네테스의 체를 '소수를 빼고 나머지는 지우는 알고리즘'이라고 생각해서 지우는 걸 이상하게 생각하신 것 같은데, 지우지 않고 남기는 것과 소수라고 판정을 하고 지우는 것은 똑같습니다.

아아 두 분다 답글 감사드립니다. 말씀하신 것처럼 지워버리니까 소수를 지우지 않고 남겨놓는 알고리즘과 헷갈렸네요 감사합니다.