유형별 정리/수학·정수론
수학·정수론O(√n)

소수 판별

약수는 짝으로 다니니, √n까지만 나눠봐도 소수인지 알아요.

이럴 때 써요

  • 수 하나가 소수인지 판단할 때
  • 약수가 1과 자기 자신뿐이라는 성질을 쓰는 문제
  • 확인할 수가 몇 개 안 될 때 — 범위 전체의 소수가 필요하면 에라토스테네스의 체가 더 빨라요

개념

소수는 1보다 크면서 약수가 1과 자기 자신뿐인 수예요. 약수도 짝으로 다니니까, n에 약수가 있다면 그중 하나는 반드시 √n 이하예요. 그래서 2부터 √n까지만 나눠보고 하나도 안 나눠지면 소수예요. O(√n)이에요.
  • 0과 1은 소수가 아니에요. 2가 가장 작은 소수예요.
  • 2는 유일한 짝수 소수예요. 이것만 예외로 처리하면 나머지 짝수는 전부 걸러도 돼요.
  • i < n 이나 i ≤ n / 2 까지 도는 것도 정답이지만 느려요. i * i ≤ n 이면 충분해요.
"29는 소수?" — √29 ≈ 5.4 까지만 확인
29 가 소수일까? i * i ≤ 29 까지만 나눠봐요
​
i=2 :  29 % 2 = 1   ≠ 0
i=3 :  29 % 3 = 2   ≠ 0
i=4 :  29 % 4 = 1   ≠ 0
i=5 :  29 % 5 = 4   ≠ 0    (5 * 5 = 25 ≤ 29)
i=6 :  6 * 6 = 36 > 29   →  멈춤
​
한 번도 안 나눠짐 → 29 는 소수예요 (true)
한 번 더 줄일 수 있어요. 2만 따로 소수로 인정하고 나머지는 홀수만 (3, 5, 7 …) 확인하면 나눗셈 횟수가 절반이 돼요. 짝수는 이미 2에서 다 걸러지니까요.

패턴 코드

√n까지 나눠보기 (짝수는 먼저 거르기)
javascript
function isPrime(n) {
  if (n < 2) return false;
  if (n < 4) return true;         // 2, 3
  if (n % 2 === 0) return false;  // 나머지 짝수는 전부 탈락
  for (let i = 3; i * i <= n; i += 2) {
    if (n % i === 0) return false;
  }
  return true;
}

이 유형으로 풀어보기

← 약수 구하기에라토스테네스의 체 →