[JS] 프로그래머스 : 소수 찾기 12921

 

 

📝 문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

🫠 나의 풀이

function solution(n) {
  let answer = 0;

  for (let i = 2; i <= n; i++) {
    if (isPrimeNumber(i)) answer++;
  }

  return answer;
}

function isPrimeNumber(number) {
  for (let i = 2; i < number; i++) {
    if (number % i === 0) return false;
  }

  return true;
}

 

시간 초과.. 🫠

 

🧞‍♂️ 다른 사람의 풀이

function solution(n) {
  let array = Array(n + 1)
    .fill(true)
    .fill(false, 0, 1);
  let count = 0;

  for (let i = 2; i <= n; i++) {
    if (array[i]) {
      count++;
      for (let j = i * i; j <= n; j += i) {
        array[j] = false;
      }
    }
  }

  return count;
}

 

 

 

🔗 https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스