에라토스테네스의 체 구현

    for(int i = 2; i*i <= n; i++){
        if(!visit[i]) continue;
        for(int j = i*i; j <=n; j+=i){
            visit[j] = false;
        }
    }
    for(int i = 2; i <= n; i++) if(visit[i]) prime.push_back(i);

원래는 에라토스테네스의 체를 위처럼 구현했다.  불필요한 연산 같아서 위의 for 문에서 i*i 를 i 로 바꾸면 출력이 안됐다.

왜 안되는지 고민하다가 백준에 넣어보니까 int overflow가 발생함을 알 수 있었다....

 

그래서 long long 형으로 바꿔주니까 잘 작동한다.

void sieve(int n){
    vector<bool> visit(n+1,1);
    for(long long i = 2; i <= n; i++){
        if(!visit[i]) continue;
        for(long long j = i*i; j <=n; j+=i){
            visit[j] = false;
        }
        prime.push_back(i);
    }
}

 

근데 뭐가 더 효율적인지는 모르겠음

 

시간 초과나는 코드에 넣어도 똑같이 시간초과나고..