소수 판정

(2020-12-07)

소수 찾기, 에라토스테네스의 체


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;
}

(기타 알고리즘)
   1. 알고리즘 용어   2. 소수 판정   3. 하노이 탑  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"