소수 판정

1. 소수의 판정

  ㅇ 에라토스테네스의 체(Eratosthenes' Sieve)가 유명
     - (2부터 시작하여, 모든 정수의 배수를 체로 거르는 방법)

  ㅇ 에라토스테라스 체 구현 例)
     - (자바스크립트)
        
function eratosthenes(n) {
1    var p = [];
2    for (var i=2; i<=n; i++) p[i] = true; // 2 ~ n까지의 모든 정수를 일단 소수로 간주
3    var max = Math.floor(Math.sqrt(n)); // 소수 x는 √n까지 구하면 됨
4    var x = 2; // 최초의 소수
5    while (x <= max) { // √n 즉, max까지 반복
6        for (var i = 2 * x; i <= n; i += x) p[i] = false; // x의 배수들을 합성수로 처리
7        while(!p[++x]) /* empty */ ; // 다음 소수 x를 찾음
8    }
9    return p;
} 
        . 2 이상 자연수 n을 입력 받고, 배열 p를 반환
           .. 배열 p 원소 각각이 소수이면 true, 합성수이면 false로 설정됨 
        . 1) 빈 배열 p 생성 ('0','1'을 제외한 n-1개 원소 필요)
        . 2) 검토 대상 숫자는 모두 일단 true로 간주(초기화)시킴
        . 3) p ≤ √n 까지의 숫자 만 고려하면 됨
        . 4) 현재 처리중인 정수로써, p를 '2'로 초기화함 
        . 5~8) 합성수를 표시하는 2중 반복문

  ㅇ 소수 판정 구현 例)
     - (개요)
        . 2 부터 시작하여 제곱근 보다 작은 수 까지, 나누어 떨어지지 않으면 소수로 판정
     - (C 언어)
        
int is_prime (int n) {
    int i;
    if (n < 2) return 0;
    for (i = 2; i*i < n; i++) {  // i < n or i < n/2 or i*i < n
        if (n % i == 0) return 0;
    }
    return i;
}
     - (자바 언어)
        
public static boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i*i < n; i++)  // i < n or i < n/2 or i*i < n
        if (n % i == 0) return false;
    return true;
}