[Algorithm/JS] 백준 1978번 소수 찾기

🔗 문제 바로가기 (opens new window)

Question

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

Input

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

Output

주어진 수들 중 소수의 개수를 출력한다.

Example

Input

4
1 3 5 7

Output

3

Solution

const [cnt, ...input] = require('fs')
  .readFileSync('dev/stdin')
  .toString()
  .trim()
  .split('\n');
const nums = input[0].split(' ').map(Number);

let result = 0;
nums.map((num) => {
  // 1
  let half = Math.ceil(num / 2); // 2
  let decimal = true; // 3
  if (num === 1) return; // 4
  for (let i = 2; i <= half; i++) {
    // 5
    if (num % i === 0) {
      // 6
      decimal = false;
    }
  }
  if (decimal) result++; // 5
});

console.log(result);

먼저 소수란 1과 자신 외의 자연수로 나눌 수 없는 1보다 큰 자연수를 말한다.

소수임을 어떻게 판별할 수 있을까?

입력받은 숫자(입력값)를 2~(입력값-1) 범위의 숫자들로 나누었을 때 나머지가 0인(나누어떨어지는) 숫자가 없다면 그 수는 소수이고, 나누어 떨어지는 있다면 그 수는 소수가 아니게 되는 것이다.

1. map 함수로 입력값을 순회한다.
2. half 변수는 입력값의 검사 범위 2~(입력값-1) 을 모두 검사할 필요가 없기 때문이다. 범위의 절반만 검사해도 소수인지 아닌지 판결할 수 있다.
3. decimal 변수는 소수인지 아닌지 판별하는 boolean 변수다. 소수라면 true, 소수가 아니라면 false
4. 4번은 예외처리다. 1은 소수가 아니기 때문에 입력값이 1이라면 decimal 은 무조건 false이며 return 문으로 map 을 빠져나온다.
5. 2부터 half 까지의 수로 반복문을 실행하고
6. 입력값(num)을 2부터 half 까지의 수로 나누었을 때 나누어 떨어지는 수는 소수가 아니다. 즉 decimal 변수는 false를 갖는다.
7. 마지막으로 decimal 가 true 라면 result 의 개수를 증가시킨다.