[알고리즘] N의 약수를 구하는 효율적인 알고리즘

만약 100의 약수의 개수를 구하고 싶다면
100의 제곱근의 약수만 확인하면 된다.

100의 제곱근은 10이므로 10의 약수는 1,2,5,10 이다.
그리고 100을 위에서 구한 약수들로 나누면된다.

100 / 1 = 100
100 / 2 = 50
100 / 5 = 20
100 / 10 = 10

이 100,50,20,10 을 위에서 구한 10의 약수들이랑 합치면 되는데
여기서 10은 중복되므로 한번만 작성해야한다.
그러면, 100의 약수는 1,2,5,10,20,50,100 이 된다.

위 방법 대로 한다면 시간 복잡도는 O(√N) 이 되므로 굉장히 빠르다.
만약 9억의 약수를 구한다고 하면 3만번의 연산만 하면 되는것이다.

go 언어로 구현하면 다음과 같다.

package main

import (
	"fmt"
	"math"
)

func main() {
	divisors := getDivisor(100)
	for i := 0; i < len(divisors); i++ {
		fmt.Println(divisors[i])
	}
}

func getDivisor(number int) []int {
	divisor := []int{}
	sqrt := int(math.Sqrt(float64(number)))
	for i := 1; i <= sqrt; i++ {
		if number%i == 0 {
			divisor = append(divisor, i)
			if i != number / i {
				divisor = append(divisor, number/i)
			}
		}
	}
	return divisor
}

Output

1
100
2
50
4
25
5
20
10