본문 바로가기
Dev Talks/Algorithm

[알고리즘 #4] 약수(divisor) 구하는 알고리즘 정리

by 곰씨네IT 2017. 3. 22.

** Responsive Ad **


1. 약수 (divisor, aliquot)

어떤 수를 나누었을 때 나머지가 0이 되는 수, 제수(除數)



2. N의 약수를 구하기 위한 접근방법


1) 1부터 N까지 차례로 나누어 나머지가 0이 되는지 확인


2) sqrt(N) 보다 작은 약수를 먼저 구한 뒤 이를 이용하여 sqrt(N) 보다 큰 약수 구하기


100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100 

sqrt(100) = 10 이므로 1,2,4,5 를 구한 뒤,

100 / 1 = 100

100 / 2 = 50

100 / 4 = 25

100 / 5 = 20 


으로 sqrt(100)보다 큰 약수를 구한다.



** 큰사각형 광고 **



댓글