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

에라토스테네스의 체

• 소수를 판별하는 알고리즘

단일 숫자의 소수 여부 확인

어떤 수의 소수 여부를 확인할 때는, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.

에라토스테네스의 체 원리

1. 배열을 생성하고 초기화
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. (자기 자신은 지우지 않고, 이미 지워진 수는 건너뛴다.
3. 2부터 시작하여 남아있는 수를 모두 출력

public class PrimeNumber2 {

     static int max = 999;
     static boolean[] prime;

     public static void main(String[] args) {
          prime = new boolean[max + 1];

          primeNum();
          for (int i = 2; i < max; i++) {
               if (!prime[i]) {
                    System.out.print(i + " ");
               }
          }
     }

     public static void primeNum() {
          prime[1] = true;
          for (int i = 2; i <= max; i++) {
               if (!prime[i]) {
                    for (int j = i + i; j <= max; j += i) {
                         prime[j] = true;
                    }
               }
          }
     }
}

소수를 출력하는 것이 아닌 단순히 판별만 하는 메서드도 만들어 낼 수 있다.

            // 소수의 갯수.
             static int answer = 0;

public static void cal(int n) {

              //0과 1은 소수가 아니므로 바로 종료.
              if (n == 0) return;
              if (n == 1) return;

              //2~n의 제곱근까지 돌면서 나누어 떨어지면 소수가 아니므로 메소드 종료.
              for (int i = 2; i <= Math.sqrt(n); i++) {
               if (n % i == 0) return;
              }

              //모두 나누어 떨어지지 않으면 소수이므로 answer 증가.
             answer++;
     }