cs-js-16-알고리즘-소수 구하기

SeungWoo Yoo ·2023년 2월 7일

JS-자료구조-알고리즘

목록 보기

16/16

1. 소수(prime) 구하기

An integer n > 1 is called a prine number, of simply a prime.
if its only positive factors are 1 and n.
An integer n > 1 that is not a prime is called composite.

1보다 큰 정수들 중, 약수로 1과 자기 자신을 갖는 것을 소수(prime)
그 밖의 수들을 합성수(composite)이라고 한다.

Algorithm_16_1

소수는 1 또는 자기 자신만은 약수로 가지는 수를 의미한다.

2. 소수를 구하는 효율적인 방법

2.1 가장 직관적인 방법

2부터 N-1까지 루프를 돌며 나눠보기

Algorithm_16_2

다른 방법들에 비해 느린 편에 속한다.

// O(n)
function is_prime(num) {
  for (let i = 2; i < num; i += 1) {
    if (num % i == 0) {
      return false
    }
  }
  return true
}

2.2 효율성 개선하기

그 어떤 소수도 N의 제곱근보다 큰 수로 나눠지지 않는다는 점을 이용

Algorithm_16_3

이전 방법보다 더 효율적이다.

// O(루트 n)
function is_prime(num) {
  for (let i = 2; i * i <= num; i += 1) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

2.3 에라토스테네스의 체⭐

Algorithm_16_4

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법으로 소수를 판단할 떄, 가장 효율적인 알고리즘

Algorithm_16_5

2를 제외한 2의 배수가 되는 수들을 모두 체크
3의 배수가 되는 수들을 모두 체크
4는 이미 체크되어 있기 떄문에 넘어감
5의 배수가 되는 수들을 모두 체크
7의 배수가 되는 수들을 모두 체크

Algorithm_16_6

8부터는 확인할 필요가 없다
이후 54까지 체크되지 않은 수들은 모두 소수로 판단

에라토스테네스의 체는 1부터 N까지 모든 소수를 구하는 경우 가장 효율적이다.

// 에라토스테네스의 체
// O(n log log n)
function get_primes(num) {
  // 0과 1을 제외한 입력값의 나머지 숫자까지 true를 담은 배열
  const prime = [false, false, ...Array(num - 1).fill(true)];
  
  // 2 ~ 입력받은 수까지 순회
  for (let i = 2; i * i <= num; i += 1) {
    // 2, 3, 4 순으로 배수들을 false로 체크
    if (prime[i]) {
      for (let j = i * 2; j <= num; j += i) {
        prime[j] = false;
      }
    }
  }
  return prime.filter(Boolean); // false같은 값을 제거
}

2.3.1 추가 설명 : filter(Boolean)

const something = [
 ...some
].filter(Boolean);

왜 이렇게 사용할까? JS에서 제공되는 배열은 아래와 같이 선언하여 사용할 수 있다.

const bad = undefined;
const bomb = [undefined, 5, null, ,,undefined];


const arr = [bad, 1, 2, ...bomb];
// arr = [undefined, 1, 2, undefined, 5, null, undefined, undefined, undefined]

위에서 제공되는 예시와 같이 undefined 또는 null이 의도하지 않게 들어갈 수 있다.
이러한 가능성은 반복문에서 문제가 발생될 가능성이 크다.

arr.map((item) => {
  console.log(item.value);  // ERROR! Uncaught TypeError: Cannot read property 'item' of undefined
})

이를 해결하기위해 일반적으로 반복문 내에서 체크하는 로직을 삽입하여 처리하기도 한다.

arr.map((item) => {
  if (item) {
    return item;
  }
  
  console.log(item.value);
})

하지만 이러한 처리방식은 두가지의 문제점을 야기한다.

코드가 복잡해진다.
배열이 또다른 새로운 배열로 확장되는 경우 또는 배열이 재사용되는 경우 동일하게 체크하는 로직을 삽입하여야한다.

이보다 더 좋은 방법은 없을까? 그 방법이 filter(Boolean)을 사용하여 배열을 믿을 수 있는 상태로 만드는 것이다! 심플하고 간단하게 사용할 수 있다.

let array = [false, 0, -0, 0n, "", null, undefined, NaN, {hello: "world"}];

console.log(array.filter(Boolean)); // [{hello: "world"}]

Boolean을 iterator 로 사용하여 false, 0, -0, 0n, "", null, undefined, NaN를 제거할 수 있다.

Reference : https://michaeluloth.com/filter-b

3. 실습 : 소수 찾기

3.1 문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

[제한 조건]

n은 2이상 1000000이하의 자연수입니다.

[입출력 예]

n	result
10	4
5	3

3.2 풀이

이 문제는 이름 그대로 1부터 입력받은 숫자 n 사이에 있는 소수를 찾는 문제입니다.
1부터 n까지 소수를 모두 찾아야할 경우 가장 효율적인 알고리즘은 에라토스테네스의 체라고 말씀드린 것 기억나시나요?
이번 문제는 에라토스테네스의 체를 이용하여 쉽게 풀 수 있습니다.

그렇지만 다른 알고리즘도 이용하여 한 번 비교해보도록 하겠습니다.

3.2.1 단순 루프로 풀어보기

단순히 2부터 N까지 루프를 도는 것으로 일단 풀어볼 수 있습니다. 코드는 다음과 같습니다.

// O(n)
function isPrime(num) {
  for (let i = 2; i < num; i += 1) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

function solution(n) {
  let answer = 0;
  for (let i = 2; i <= n; i += 1) {
    if (isPrime(i)) {
      answer += 1;
    }
  }
  return answer;
}

하지만 이 코드의 경우 성능이 느리기 때문에 모든 테스트 케이스를 통과하지 못합니다. 따라서 더 효율적인 방법을 찾아야 합니다.

3.2.2 제곱근 이후 연산하지 않기

영상에서 말씀드린 것처럼 N의 제곱근 이후는 체크할 필요가 없습니다. 따라서 다음과 같이 코드를 개선합니다.

// O(sqrt(n))
function isPrime(num) {
  for (let i = 2; i * i <= num; i += 1) {
    // 이 부분이 변경됩니다.
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

function solution(n) {
  let answer = 0;
  for (let i = 2; i <= n; i += 1) {
    if (isPrime(i)) {
      answer += 1;
    }
  }
  return answer;
}

정확성 테스트는 모두 통과하지만 여전히 효율성 테스트는 통과하지 못합니다. 따라서 더 효율적인 알고리즘을 사용해야 합니다.

3.2.3 에라토스테네스의 체

에라토스테네스의 체를 구현한 코드는 다음과 같습니다.

// 에라토스테네스의 체
// O(n log log n)
function get_primes(num) {
  // 0과 1은 소수가 아니기에 미리 false로 체크합니다.
  const prime = [false, false, ...Array(num - 1).fill(true)];

  for (let i = 2; i * i <= num; i += 1) {
    if (prime[i]) {
      for (let j = i * 2; j <= num; j += i) {
        prime[j] = false;
      }
    }
  }
  return prime.filter(Boolean); // true만 필터링하고 싶을 경우 이런 방식으로 쓸 수 있습니다.
}

function solution(n) {
  return get_primes(n).length;
}

이 경우 효율성 테스트를 통과합니다. 정확도 테스트에서 걸린 시간을 확인해보아도 훨씬 빠르다는 것을 알 수 있습니다.

SeungWoo Yoo

Front-end 공부 중... 책 읽는 걸 좋아합니다.

이전 포스트