소수 (Prime) - JavaScript

 

코딩테스트 스터디에 들어갔다. 문제를 자주 푸는 습관을 만들어갈 수 있을 것 같다.

 

오늘은 JS를 활용해서 주어지는 두 수 사이의 소수를 구하는 함수를 이해한 바를 정리하고,

백준 문제 1929번에 제출한 답안 기록한다.

 

소수 (Prime Number)

소수는 1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 가지는 수를 의미한다.

그렇기 때문에 아래와 같은 특징들을 갖는다.

• 소수는 항상 두 개의 약수(1과 자신)만을 가진다.
• 2를 제외하고는 모든 소수는 홀수이다.
• 소수의 자연수 내에서 규칙적으로 나타나지 않으며, 분포가 불규칙적이고 개수는 무한하다.

JS 구현

입력값을 정렬하여 역순 입력도 대응 가능하다.

소수를 판별하는 함수인 isPrime을 분리하여 구현하였다.

범위 내 각 숫자에 대해 소수를 판별하여 배열에 저장 후 반환한다..

• 2는 유일한 짝수 소수로 즉시 반환
• 짝수는 즉시 제외
• 3부터 숫자의 제곱근까지 홀수만 검사하여 효율성 향상

function findPrimesInRange(start, end) {
  // 소수 판별 함수
  const isPrime = (num) => {
    if (num <= 1) return false;
    if (num === 2) return true;
    if (num % 2 === 0) return false;

    // 3부터 제곱근까지 홀수로 나눠보기
    for (let i = 3; i <= Math.sqrt(num); i += 2) {
      if (num % i === 0) return false;
    }
    return true;
  };

  // 범위 조정 및 결과 저장
  const [lower, upper] = [Math.min(start, end), Math.max(start, end)];
  const primes = [];

  // 범위 내 모든 숫자 검사
  for (let num = lower; num <= upper; num++) {
    if (isPrime(num)) primes.push(num);
  }

  return primes;
}

// 사용 예시
console.log(findPrimesInRange(3, 16)); // [3, 5, 7, 11, 13]

 

 

백준 1929번 문제: 소수 구하기

범위 조정 및 결과를 primes 배열을 사용하는 부분을 제거하고 바로 console.log를 찍었다.

const [start, end] = require('fs').readFileSync('/dev/stdin').toString().trim().split(" ").map(Number);

const isPrime = (num) => {
  if (num <= 1) return false;
  if (num === 2) return true;
  if (num % 2 === 0) return false;

  for (let i = 3; i <= Math.sqrt(num); i += 2) {
    if (num % i === 0) return false;
  }

  return true;
};

for (let num = start; num <= end; num++) {
  if (isPrime(num)) console.log(num);
}

 

맞기는 했는데 2772 ms 시간이 소요됐다.

[출처 2] 같은 경우는 시간이 내 1/10 수준인 224ms 밖에 안걸렸다. 😮

나중에 살펴보고 어떤 부분에서 내가 더 시간이 더 걸리는지 알아봐야 겠다.

 

 

 

출처 1. [백준] 1929번: 소수 구하기

출처 2. 기록하는 즐거움: [백준] 1929: 소수 구하기 (javascript)