// (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로써 마킹된, 숫자 배열을 리턴
}