[Algorithm] 에라토스테네스의 체

목차

1. 2 ~ n까지 방문여부를 판단하는 boolean 배열 b 생성

2. 처음에는 모든 숫자를 소수로 판별해서 b를 true로 전부 초기화

3. 만약 b[i]가 true이면 i는 소수이고, i의 배수들은 소수가 아니므로 false의 값을 준다

4. 만약 b[i]가 false이면, i는 이미 소수가 아니므로 i의 배수들 역시 소수가 아니다, 이러면 검사할 필요가 없다

static void Eratos (int n){
        if(n<=1) return;
 
        eratos = new boolean[n+1];
 
        for(int i=2; i<=n; i++)
            eratos[i] = true;
 
        for(int i=2; i*i<=n; i++){
            if(eratos[i]){
                for(int j=i*i; j<=n; j+=i)
                    eratos[j] = false;
            }
        }
    }