[C++] 에라토스의 체

소수 판별 알고리즘

1. N 이 소수인지 판별하려면 N-1 까지 for 문을 돌 필요없이 N 의 제곱근까지만 확인
2. 현재 숫자가 방문하지 않은 숫자라면 소수라고 판단하고 해당 소수의 배수들은 모두 방문처리 해주기
   ❗️ 단, 중복해서 방문하는 경우를 방지하기 위해 배수를 지워줄 때는 현재 소수의 제곱수부터 지우기 시작
   ex) 2의 배수를 지우고 3의 배수를 지운다면 2*3 은 이미 지워졌기 때문에 3*3 부터 배수를 지우기 시작하는 것
3. 이후, 방문처리되지 않은 숫자는 소수만 남게 됨

✏️ code

for(int i = 2; i*i <= N; i++) {
        
   if(arr[i]==0) {
       for(int j = i*i; j<=N; j+=i) {
           arr[j] = 1;
       }
   }