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