일반적으로 특정 수 n이하의 수 중에서 소수인 수를 찾는 경우에는 여러 가지 방법이 존재하지만, 그 중 가장 효율적인 방법을 소개한다.
예시) 10000 이하의 수 중에서 소수인 수 찾기
let maxNum = 10000;
let sqrt = Math.ceil(Math.sqrt(maxNum));
// => 10000의 제곱근의 올림
let isPrime = new Array(maxNum + 1).fill(true);
// => 0부터 10000번까지의 index를 갖는 배열로
// 해당 index가 소수인지 아닌지의 여부를 원소에 기록하는 배열
// 기본적으로 0부터 10000까지 모든 수가 소수라고 가정하므로 값을 true로 초기화하고,
// 0부터 10000까지의 수 중에서 소수가 아닌 수를 찾아 값을 false로 변경한다.
isPrime[0] = false;
isPrime[1] = false;
// => 0과 1은 소수가 아니므로 false로 초기화
let i = 2;
// => 2의 배수부터 시작
// 소수가 아닌 수는 특정 수의 배수임을 이용하여 소수가 아닌 수를 찾아내 false로 값을 변경한다.
// ex) 소수가 아닌 수 4는 특정 수의 배수(2를 2배한 수)임
// i의 n배수를 찾는 과정
while (i <= sqrt) {
// => i는 위에서 설명한 특정 수이며, 계산에서 2의 배수부터 제곱근(올림)의 배수까지 사용되므로
// 2부터 제곱근(올림)까지 증가함
for (let j = i + i; j <= maxNum; j = j + i) {
// => j는 i의 배수(2배수부터 시작)이며, maxNum과 같거나 작다면 반복함
// j = i*2, j = i*3, j = i*4, ...
isPrime[j] = false;
// => j는 i의 배수이므로, 1과 자신(j) 말고도 i라는 약수가 있기 때문에 소수가 아님
// 따라서 isPrime[j]를 false로 변경함
}
i++;
}
결론 : 위 방법을 이용하면 특정 수 이하의 수에 대해 소수 여부를 기록한 isPrime 배열을 만들 수 있다.