🧮

Is Prime

Is Prime - Explanation

쉬움 알고리즘 O(sqrt(n)) O(1)

Problem Summary

Write a function that checks if a number is prime.

Go to Problem →

Detailed Explanation

이 문제는 **소수 판별 알고리즘**과 **제곱근 최적화**를 학습합니다. ## 핵심 개념: 소수 (Prime Number) 소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다. ### 접근 방법 ```javascript function isPrime(n) { if (n < 2) return false; for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) return false; } return true; } ``` ### 제곱근 최적화 n = a * b일 때, a와 b 중 하나는 반드시 √n 이하입니다. - 36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6 - √36 = 6이므로 6까지만 확인하면 됨 ### 시간 복잡도 비교 - 모든 수 확인: O(n) - 제곱근까지: O(√n) ← 훨씬 효율적! ### 특수 케이스 - 1은 소수가 아닙니다 - 2는 유일한 짝수 소수입니다 - 음수는 소수가 아닙니다 소수 판별은 암호학의 기초가 되는 중요한 알고리즘입니다.

Solution Code

solution.js
function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}

Key Concepts from This Problem

1. 소수 판별
2. 제곱근 최적화
3. Math.sqrt
4. 나눗셈 검사

Common Mistakes

✗ 1은 소수가 아닙니다
✗ 2는 확인해야 하는 최소 소수입니다
✗ 제곱근까지만 확인하면 되는 이유를 이해해야 합니다

Hints

Hint 1: 2부터 제곱근까지만 확인하면 됩니다.

Complexity Analysis

Time Complexity

O(sqrt(n))

Space Complexity

O(1)

Uses almost no additional memory

Related Tags

#알고리즘 #소수 #수학
Solve Problem Other Problems