[JS] 소수 찾기

[풀이]

이번 문제는 어려웠던 문제였음!

1. 소수찾는 법을 알아야했다. (소수찾는 법을 알아도 문제를 풀기가 힘들었다)

2. 풀이가 여러가지 방법이 존재한다.

function solution(n) {
  const nArr = new Array(n).fill(1);

  nArr[0] = 0;

  for (let i = 2; i * i <= n; i++) {
    for (let j = i * i; j <= n; j += i) {
      nArr[j - 1] = 0;
    }
  }
  return nArr.filter((result) => result == 1).length;
}

1. n개수 만큼의 배열을 만들어 모두 1로 채워서 넣음

2. 1은 소수가 아니므로 배열 안에서 값을 0으로 변경해줌 (nArr[0] = 0;)

3. 2부터 제곱근으로 순회해 2의 배수를 모두 0으로 변경 

4. 다시 3으로 순회할 경우 3의 배수를 모두 0으로 변경

5. 결국 소수는 1로 남게 될 것. filter()함수로 1인 값만 반환해 개수를 알 수 있음!

 

[다른 팀원의 풀이]

const primeNumber = (x) => {
  for (let i = 2; i <= Math.sqrt(x); i++) {
    if (x % i === 0) return false;
  }
  return true;
};

function solution(n) {
  let result = 0;

  for (let i = 2; i <= n; i++) {
    if (primeNumber(i)) result++;
  }
  return result;
}

이 때 Math.sqrt() 는?

double타입의 인수를 전달하면 인수에 대한 double타입의 제곱근 값 리턴

제곱근은 음수가 나올 수 없으므로 음수 입력시 NaN 리턴

Math.sqrt(double d);    //d의 제곱근 출력함

Math.sqrt(9); // 3
Math.sqrt(20); // 4.47213595499958

 

[리더님 풀이]

function solution(n) {
  let result = 0;

  for (let i = 2; i <= n; i++) {
    if (checkDecimals(i)) {
      result++;
    }
  }
  return result;
}

function checkDecimals(num) {
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
}

/**
 * (풀이 설명)
 * 1부터 입력받은 숫자 n사이에 소수의 개수를 반환하는 문제이다.
 * 따라서 첫번째 for문에서 2부터 n까지 순회하면서 소수인지 검증한다. 이때, 1은 소수가 아니므로 제외한다.
 * for문을 돌리면서 checkDecimals를 호출하는데, 여기서도 for문을 통해 나누어 떨어지는지 검증한다.
 * 이때 제곱근까지 나누어 떨어지지 않으면 해당 숫자는 소수이기 때문에 Math.sqrt()를 통해 제곱근까지만
 나눠서 반복하는 횟수를 줄여줘야 한다.
 * 예1) 5 같은 경우 5의 제곱근은 2.xx인데 3과 4는 어차피 안나눠짐 의미없기 때문에 생략
 * 예2) 9 같은 경우 9의 제곱곱은 3인데 3 이후로 4 ~ 8은 안나눠짐 의미없음
 */