수학·정수론O(√n)

약수 구하기

약수는 짝으로 다녀요. √n까지만 훑어 O(√n)에 끝내요.

이럴 때 써요

어떤 수의 약수 개수나 목록이 필요할 때
가로 × 세로 = 넓이 처럼 곱해서 특정 값이 되는 두 수를 찾을 때 — 후보는 약수뿐이에요
약수의 합·완전수처럼 약수를 모두 더하거나 세는 문제

개념

약수는 항상 짝으로 다녀요. i가 n의 약수면 n / i도 약수예요. 그래서 1부터 n까지 다 볼 필요 없이, 짝 중 작은 쪽인 i * i ≤ n 범위만 훑고 큰 짝은 n / i로 바로 얻으면 돼요. O(n)이 O(√n)으로 줄어요 — n이 10억이어도 3만 번 남짓이에요.

"36의 약수" — i는 작은 쪽, n/i는 큰 쪽
n = 36, i * i ≤ 36 까지만 훑어요
i=1 :  36 % 1 = 0   →  1 ↔ 36
i=2 :  36 % 2 = 0   →  2 ↔ 18
i=3 :  36 % 3 = 0   →  3 ↔ 12
i=4 :  36 % 4 = 0   →  4 ↔ 9
i=5 :  36 % 5 = 1   →  나눠지지 않음, 건너뛰어요
i=6 :  6 * 6 = 36   →  6 ↔ 6, 자기 자신이라 한 번만
i=7 :  7 * 7 = 49 > 36 이라 멈춰요
작은 쪽 1 2 3 4 6  +  큰 쪽 9 12 18 36 뒤집기
→ [1, 2, 3, 4, 6, 9, 12, 18, 36]

정렬도 공짜예요. 작은 약수는 1, 2, 3 … 오름차순으로 나오고, 큰 짝은 … 18, 12, 9 내림차순으로 나와요. 큰 쪽만 따로 모아 뒤집어 붙이면 정렬 함수 없이 오름차순이 완성돼요.

방법	훑는 횟수	복잡도
`1`부터 `n`까지	n 번	`O(n)`
`√n`까지 짝으로	√n 번	`O(√n)`

패턴 코드

제곱근까지 훑으며 짝으로 모으기작은 약수는 small에, 큰 짝은 large에 모았다가 뒤집어 붙여요. i * i === n 인 제곱수만 한 번 담기게 걸러요.

javascript
Copy code
function divisors(n) {
  const small = [];
  const large = [];
  for (let i = 1; i * i <= n; i++) {
    if (n % i !== 0) continue;
    small.push(i);
    if (i !== n / i) large.push(n / i);
  }
  return small.concat(large.reverse());
}

이 유형으로 풀어보기

소수 판별 →