백준 1978번

백준 1978번을 풀어보았다.

 

앞서 약수를 찾을 때 1부터 N까지 확인해 볼 수도 있지만 1부터 N의 제곱근까지만 확인해도 된다고 하였는데,

 

소수 여부를 판단하고 소수를 찾는 경우에도 동일하다.

 

소수라는 건 1과 자기자신을 제외한 약수를 가지지 않는 수를 의미하므로

 

2부터 자기자신-1까지 중 약수가 존재하지 않으면 소수일 것이다.

 

이때 약수는 대칭적으로 존재하므로 2부터 자기자신의 제곱근까지 중 약수가 존재한다면

 

자기자신의 제곱근 이후로는 굳이 확인해 볼 필요 없다.

 

참고) 백준 2501번, 백준 9506번

 

1부터 input[i]까지 확인하기

let [N, input] = require('fs').readFileSync('/dev/stdin').toString().split('\n')

N = Number(N)
input = input.split(' ').map(Number)

let output = 0

for (let i = 0; i < N; i++) {
  let isPrimeNumber = true

  if (input[i] === 1) {
    isPrimeNumber = false
  } else {
    for (let j = 2; j < input[i]; j++) {
      if (input[i] % j === 0) isPrimeNumber = false
    }
  }
  
  if (isPrimeNumber === true) output += 1
}

console.log(output)

 

1부터 input[i]의 제곱근까지 확인하기

let [N, input] = require('fs').readFileSync('/dev/stdin').toString().split('\n')

N = Number(N)
input = input.split(' ').map(Number)

let output = 0

for (let i = 0; i < N; i++) {
  let isPrimeNumber = true

  if (input[i] === 1) {
    isPrimeNumber = false
  } else {
    for (let j = 2; j <= Math.sqrt(input[i]); j++) {
      if (input[i] % j === 0) isPrimeNumber = false
    }
  }
  
  if (isPrimeNumber === true) output += 1
}

console.log(output)

 

이때, for (let i = 0; i < N; i++) 대신 filter 메소드로 배열을 반복할 수도 있다.

let [N, input] = require('fs').readFileSync('/dev/stdin').toString().split('\n')

N = Number(N)
input = input.split(' ').map(Number)

let primeNumbers  = []

primeNumbers = input.filter((value) => {
  if (value === 1) return false

  for (let i = 2; i <= Math.sqrt(input[i]); i++) {
    if (value % i === 0) return false
  }

  return true
})

console.log(primeNumbers.length)

 

filter 메소드를 사용한 풀이를 오랜만에 봐서 정리해 봤다.

 

forEach, map, filter 메소드 모두 잘 알고는 있지만 코드를 작성하다 보면 자꾸 익숙한 반복문, 조건문만 사용하게 된다.

 

 메소드들도 적재적소에 자유자재로 사용할 수 있도록 노력하자!