[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

일반적으로 짜는 방법은 O(N lg lg N)인데, 리스트를 사용해 O(N)으로 시간복잡도를 줄인 버전이다.

친구가 짜서 준 소스를 조금 다듬었다.

#include <cstdio>

const int MAX=1000020;

int n, next[MAX], prev[MAX];

int main(){
    int i, j;

    scanf("%d", &n);

    for(i=1; i<n+3; i++){
        next[i] = i+1;
        prev[i] = i-1;
    }

    for(i=2; i*i<=n; i=next[i]){
        for(j=i; i*j<=n; j=next[j]);
        for(j=prev[j]; j!=i; j=prev[j]){
            prev[next[i*j]] = prev[i*j];
            next[prev[i*j]] = next[i*j];
        }
        prev[next[i*i]] = prev[i*i];
        next[prev[i*i]] = next[i*i];
    }

    for(i=2; i<=n; i=next[i])
        printf("%d ", i);
}