소인수분해로 약수 구하는 법
2020. 1. 8.
이전 글에서는 소인수분해를 활용해서 약수의 개수 구하는 법을 알아보았는데, 이번에는 그냥 약수 구하는 법을 알아보자. 일단 약수는 나누었을 때, 나머지가 0이 되는 수를 말하는데, 예를 들어 숫자 8이 있다고 해보자. 그럼 8은 1로 나누었을 때 나머지가 0이고, 2로 나누었을 때 나머지가 0이고, 4로 나누었을 때 나머지가 0이고, 8로 나누었을 때 나머지가 0이기에, 숫자 8의 약수는 1, 2, 4, 8이라는 것을 알 수 있다.그런데 숫자 8은 크기가 작아서 약수를 쉽게 구할 수 있지만, 숫자가 큰 경우에는 약수를 구하기가 힘들다. 예를 들어 숫자 512의 약수를 모두 구한다고 한다면? 아마도 나누기를 많이 해야 하므로, 약수를 구하기가 힘들 것이다. 하지만 이때 소인수분해를 활용하면 약수를 쉽게 구..