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

// (2022.9.24, 차재복, Cha Jae Bok, http://www.ktword.co.kr)

// (입출력) 에라토스테네스의 체로 걸러낸 소수 배열의 출력
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+' 보다 작거나 같은 모든 소수 : ';
    p.filter( x => x ).join(',');
//    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로써 마킹된, 숫자 배열을 리턴
}