[300] 1978번 소수 찾기

1978번 소수 찾기

문제

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

입력

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

출력

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

예제 입력 1 복사

4
1 3 5 7

예제 출력 1 복사

3

코드

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
4
1 3 5 7
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//

const t = Number(input());
const numberArr = input().split(' ').map(Number);

const isPrime = n => {
  if (n <= 1) return false;
  for (let i = 2; i * i <= n; i++) {
    // i * i <= n 을 i <= n / i 로 대체 가능
    if (n % i === 0) return false;
  }
  return true;
};

const primeArr = numberArr.filter(n => isPrime(n));

console.log(primeArr.length);

풀이

소수 : 1과 자기 자신만을 약수로 갖는 수

반복문 범위

• n의 약수는 n의 절반을 넘길수 없다. i <= n / 2

• i * i <= n , i <= Math.sqrt(n) , (훨신 더 빠르다.)

소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다는 방법으로 검사할 데이터를 제곱근 개 이하로 줄 일 수 있는 방법입니다.

출처: https://www.it-note.kr/308 [IT 개발자 Note]