소스 파일 : /algorithm/sieveOfEratosthenes.js (2021-01-12)     소스 설명 : (알고리즘) 에라토스테네스의 체
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
// (2021.1.12, 차재복, Cha Jae Bok, cjbword@gmailcom)

// 에라토스테네스의 체로 걸러낸 소수 배열의 출력
function showSieveOfEratosthenes(that) {
    // 입력 키 확인 및 입력 값 추출
    if(that.nodeName=='INPUT' && window.event.keyCode != 13) return;
    let n = ( that.nodeName=='INPUT' ? that.value : that.previousElementSibling.value );
    // 정수 변환
    n = Number.parseInt(n);
    // 검증
    if(!Number.isInteger(n) || n < 2) { alert('정수 (n>1) 입력'); return; }

    // 에라토스테네스의 체 호출 및 출력
    let p = sieveOfEratosthenes(n);
    let outText = '정수 '+n+' 보다 작거나 같은 모든 소수 : ';
    for(index in p) 
        if(p[index]) outText += index + ' ';
    alert(outText);
}

// 에라토스테네스의 체
function sieveOfEratosthenes(n) {
    let p = [];                             // 빈 배열 선언
    p[0] = false, p[1] = false;             // (초기화) 수 0,1을 비 소수(false)로 처리함
    for (var i=2; i<=n; i++) p[i] = true;   // (초기화) 2 ~ n까지의 모든 정수를 소수(true)로 간주
    let x = 2;                              // 최초의 소수 2부터 시작 변수
    while (x**2 <= n) {                     // 외부 루프 : √n번 반복
        for (let i = x; i <= n/x; i += 1)   // 내부 루프 : i <= n/x 까지 반복
            p[i*x] = false;                 // x의 배수들을 (i <= n/x 까지) 합성수(false)로 처리
        while(!p[++x]) ;                    // 다음 소수(true)로써, 조사대상인 x를 찾아 이동
    }
    return p;                               // 찾아낸 소수들이 true로써 마킹된 배열로 리턴
}


Copyrightⓒ written by 차재복 (Cha Jae Bok)    

   소스 이력    소스 폴더    소스 언어