Skip to main content

[Java] 소수판별 - 에라토스테네스의 체

1. 소수란?

소수(Prime Number)는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이다.
즉, 나누어 떨어지는 수가 딱 두 개인 숫자이다.

  • 예시) 2(가장 작은 소수, 유일한 짝수 소수), 3, 5, 7, 11, 13, 17, 19, 23 ...

2. 에라토스테네스의 체

각 소수의 배수를 지워서 소수가 아닌 수를 걸러낸다.
배수 지우기는 소수 자체부터 시작하지 않고, 그 소수의 제곱수부터 시작한다. - (i * i)부터
i * i <= n까지 반복하는 이유는 그 이상은 이미 배수로 걸러졌기 때문이다.
루트n까지만 검사하는 이유는 그 이상은 이미 작은 소수의 배수로 지워졌기 때문이다.

public class Solution {
    public boolean[] sieve(int n) { // sieve(체)
        boolean[] isPrime = new boolean[n + 1]; 
        Arrays.fill(isPrime, true);  // 처음에 모두 소수(true)로 가정
        isPrime[0] = false;
        isPrime[1] = false;
        
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) { // isPrime[i]가 ture면 i는 소수
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;  // i의 배수는 소수가 아님
                }
            }
        }
        
        return isPrime;
    }
}
  • 2는 가장 작은 소수니까, 2부터 시작해서 2의 배수를 모두 지워버린다. (2 제외)
  • 2 다음으로 남은 수 중 가장 작은 수가 3이다. 3의 배수를 모두 지운다.
  • 이 과정을 루트 n까지 반복하면 남은 수들이 모두 소수가 된다.
Solution sol = new Solution();
boolean[] primes = sol.sieve(100);
for (int i = 2; i <= 100; i++) {
    if (primes[i]) {
        System.out.print(i + " ");
    }
}


Back to top