[JS] 소수 찾기

JongHoon Son·2022년 7월 1일
0

JS

목록 보기
8/9
post-thumbnail

일반적으로 특정 수 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 배열을 만들 수 있다.
profile
FE 공부

0개의 댓글