에라토스테네스의 체

🚨오늘의 학습🚨

⭐️ 에라토스테네스의 체 ⭐️
→ 시간복잡도: O(N log log N)

boolean[] isPrime = new boolean[N+1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false; // 0과 1은 소수 아님

for (int i = 2; i * i <= N; i++) {
    if (isPrime[i]) { // 아직 지워지지 않았다면 소수
         
        //🎓) 왜 i*i부터 시작하냐???
        for (int j = i * i; j <= N; j += i) {
        	// j 👉🏻 i*i, i*(i+1), i*(i+2), i*(i+3)
            isPrime[j] = false; // i의 배수 제거
        }
    }
}

🎓 왜 i*i부터 시작하냐?
i1, i2, ..., i*(i-1)은
이미 작은 소수들의 배수에서 지워졌기 때문에 중복 제거를 위해 생략