[node.js] 1978 소수 찾기 (자바스크립트) 기본수학단계2

1978 소수 찾기

아래와 같이 첫 줄에 갯수 N과 다음 줄에 수를 N 개 입력받습니다. 소수가 몇 개인지 출력하시오.

4
1 3 5 7

결과

3

 

제출한 답

const [a, b] = require("fs").readFileSync("dev/stdin").toString().split("\n");

function prime(n) {
  if (n == 1) {
    return false;
  }
  for (i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

console.log(b.split(" ").filter((n) => prime(n)).length);

 

코드설명

• function prime(n) { 
  어떤 숫자 x가 소수인지를 판별하기 위해서는 2부터 x-1 까지를 나누었을때 나머지가 0인 경우가 없으면 됩니다.
  예시로
  9의 경우 9%2=1, 9%3=0  >>>  3으로 나눈 나머지가 0입니다. 소수가 아닙니다. false
  5의 경우 5%2=1, 5%3=2, 5%4=1 >>> 2, 3, 4로 나누어 봤지만 나누어 떨어지지 않습니다. 소수입니다. true
  4의 경우 4%2=0  >>> 2로 나눈 나머지가 0입니다. 소수가 아닙니다. false
•   if (n == 1) {
      return false;
    1은 소수가 아니기 때문에 제외합니다.
•   for (i = 2; i * i <= n; i++) {
      if (n % i == 0) {
        return false;
  소수를 찾기 위해서는 약수의 중간값까지만 나누어도 알 수 있습니다.
  예시로
  20의 약수는 1 2 4 5 10 20 입니다. 약수의 중간값은 4와 5입니다. >
  10과 20은 중간값까지만의 약수(4와 5)로도 나누어집니다. >
  20의 제곱근은 4와 5사이의 값입니다. > 
  따라서 i * i <= n 까지만 for 문을 반복 시키면 됩니다.
  시도해야할 횟수가 찾으려는 수만큼이 아닌, 찾으려는 수의  제곱근 값만큼으로 줄어듭니다.
•   return true;
  for 문을 다 돌았지만 false가 반환이 되지 않았다면 소수입니다. true를 반환합니다.
• .filter((n) => prime(n)).length
  filter 함수로 해당 값이 true 인 경우 리스트 b의 배열로 반환합니다. 그리고 b의 길이를 반환합니다.