이번글에서는 소수인지 확인하기를 에라토스테네스의 체와 재귀함수를 이용하여 구현해본다.

에라토스테네스의 체

양의 정수 n이 합성수라면, n의 소인수 중에는 √n보다 작거나 같은 소인수(소수인 약수)가 존재한다.
예를 들면 30은 합성수이다. 30의 약수 중에는 3이 있는데 3은 √30(= 5.5) 보다 작다.
에라토스테네스의 체는 어떤 큰 자연수가 소수인지 아닌지 알아볼 때 쓸 수 있는 방법이다.

풀이방법

• 예시1
  1001 => √1001 = 31
  31보다 작거나 같은 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 이다.
  1001을 위의 소수로 나누어 떨어지는 수가 있으면 소수가 아니다.
  1001은 7로 나누어 떨어지므로 소수가 아니다.

• 예시2
  911 => √911 = 30
  30보다 작거나 같은 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 이다.
  911은 29까지의 소수로 나누어 떨어지는 수가 없으므로 소수이다.

재귀함수를 이용하기에 n값을 소수로 나누어 떨어질 때까지 계속 반복한다.
단, 비교하는 소수가 √n보다 크면 중지한다.

prime(n) : n이 소수인지 확인하는 함수

n % 1번째 소수
n % 2번째 소수
n % 3번째 소수
n % 4번째 소수

위의 식을 일반화한 규칙으로 표시하면 아래와 같다.

prime(n) = (n % 소수[i])

    private static int prime(int n) {
        
        int result = (int) Math.sqrt(n);
   
        // 에라토스테네스의 체로 나누어 떨어지는지 확인
        for(int i=0; i<primes.length; i++) {

            // √n의 값이 비교하는 소수보다 크면 중지
            if(result < primes[i])
                 return 0;

            // n값이 소수로 나누어지면 그 소수가 약수이다.
            if(n % primes[i] == 0)
                return primes[i];
            
        }
        return 0;     
    }       
}

소스보기

소스로딩 실패

실행결과