posts/algo-42/

[utterances-bot]

알고리즘 - 에라토스테네스의 체 : 소수(prime number)와 소인수분해 | ChanBLOG

컴퓨터/IT/알고리즘 정리 블로그

https://chanhuiseok.github.io/posts/algo-42/

[NaSangWon]

감사합니다!

[NaSangWon]

int u = 2 * x 를 int u = x로 고쳤습니다. 이렇게 하지 않으면 소수의 배수인 4, 8, 16...은 체크가 되는데 정작 2는 체크가 되지 않지 않을까요?

for(int x = 2; x <= n; x++){
    if(sieve[x] == 1) continue;
    for (int u = x; u<=n; u+=x){
        sieve[u] = 1; 
    }
}

[ChanhuiSeok]

@NaSangWon 안녕하세요 :) sieve 배열의 값이 0이면 소수, 1이면 소수가 아닌 숫자라는 의미인데 말씀주신 대로 int u = x로 하면 sieve[2] = 1이 될 것 같습니다.