소수, 약수 구하기

매일 알고리즘을 포스팅하면서 20개의 문제들을 올렸고, 16개 정도의 문제를 풀었습니다. 문제를 풀어나가면서 주기적으로 나오는 단어들이 보였습니다. 소수, 약수, 합, 개수. 이 단어들이 나오면 어려웠던 부분은 알고리즘 구성이 아니었습니다. 큰 수 또는 많은 수들을 반복문으로 돌리는 일이었습니다.

해당 문제를 해결하기 위해서 반복하는 횟수를 줄이고, 더 성능이 좋은 조건을 찾아 적용하며 최대한 간단하고 최대한 기본적으로 접근했습니다.

code1

const isPrime = (num) => {
  const sqrt = Math.sqrt(num)

  let i = 2
  let check = true

  while (i <= parseInt(sqrt)) {
    if (num % i === 0) {
      check = false

      break
    }

    i++
  }

  return check
}

해당 소스는 소수인지를 확인하는 함수입니다. 확인할 임의의 자연수 num을 넣으면 소수인지 아닌지를 판별합니다.

code2

const count = (num) => {
  const sqrt = Math.sqrt(num)

  let i = 1
  let c = sqrt === parseInt(num) ? 1 : 0

  while (i <= sqrt) {
    if (num % i === 0) c += 2

    i++
  }

  return c
}

code2는 약수의 갯수를 구하는 함수입니다. 임의의 자연수 num의 약수의 개수를 return 출력합니다.

수학으로 보면 소수와 약수의 관계는 약수가 1과 자신만으로 구성되면 소수입니다.

서로의 상관관계가 있기에 실제 코드를 비교하니 굉장히 유사합니다.

그리고 공통적으로 보이는 하나의 특징이 있는데 전체를 비교하지 않고, 제곱근까이만 비교를 합니다.

만약 전체를 비교할 경우 너무 많은 반복을 하게 됩니다. 그래서 약수들의 중간지점까지만 비교하게 작성했습니다.