[알고리즘] 약수 구하기

약수를 구할 때 제곱근을 사용하는 이유
정수 n의 모든 약수를 효율적으로 찾기 위해 제곱근을 활용하는 것은 알고리즘의 성능을 크게 향상시킵니다. 이 접근법은 약수를 찾는 과정에서 불필요한 반복을 줄여 계산 시간을 단축시킵니다. 아래에서 제곱근을 사용하는 이유와 그 원리를 자세히 설명하겠습니다.

1. 약수의 쌍 관계 이해하기
   모든 약수는 쌍을 이룹니다. 예를 들어, n = 36인 경우 약수는 다음과 같습니다:

1 × 36 = 36
2 × 18 = 36
3 × 12 = 36
4 × 9 = 36
6 × 6 = 36
이처럼 약수는 항상 쌍을 이루며, 이 쌍 중 하나는 sqrt(n) 이하이고 다른 하나는 sqrt(n) 이상입니다. sqrt(n)은 n의 제곱근을 의미합니다.

2. 제곱근을 활용한 약수 찾기 알고리즘의 원리
   알고리즘 단계:

반복 범위 축소:
i를 1부터 sqrt(n)까지 반복합니다.
각 i에 대해 n % i == 0인지 확인합니다.
약수 쌍 추가:
i가 n의 약수라면, n / i도 약수입니다.
이때, i와 n / i를 모두 약수 목록에 추가합니다.
예시:

n = 36일 때:

i = 1: 1 × 36 = 36 → 약수 추가: 1, 36
i = 2: 2 × 18 = 36 → 약수 추가: 2, 18
i = 3: 3 × 12 = 36 → 약수 추가: 3, 12
i = 4: 4 × 9 = 36 → 약수 추가: 4, 9
i = 6: 6 × 6 = 36 → 약수 추가: 6 (중복 제거)
이렇게 하면 모든 약수를 효율적으로 찾을 수 있습니다.