티끌모아태산 티끌모아태산

약수

• 검사 범위 최소화하여 약수 구하기

  알고리즘 2024. 6. 8. 22:22

  자연수 $N$의 약수를 구해보자.먼저 $i=1,2,3,4\cdots \lfloor \sqrt{N}\rfloor$일 때, $N$을 $i$로 나눕니다. 만약 $Nmodi=0$ 이라면 $i$는 $N$의 약수. $$i|N$$ $i$가 약수라면 $N/i$도 약수입니다.  $$\frac{N}{i}|N$$ 그 이유는 $N$의 약수들은 항상 쌍으로 존재하기 때문입니다. 예를 들어 $12$가 $3$로 나누어 떨어지면 $3$도 $12$의 약수이고, $\frac{12}{3}$도 $N$의 약수입니다. 이 두 약수는 곱해서 $12$이 됩니다. $$i\times \frac{N}{i}=N$$ 범위가 \(\left \l..

  Read More