소인수분해로 약수의 개수 구하는 법
2020. 1. 6.
일단 약수는 “나누었을 때 나머지가 0이 되는 수”를 말한다. 예를 들어 숫자 8은, 1로 나누었을 때 나머지가 0이고, 2로 나누었을 때 나머지가 0이고, 4로 나누었을 때 나머지가 0이고, 8로 나누었을 때 나머지가 0이기에, 숫자 8의 약수는 1, 2, 4, 8이다. 그래서 8의 약수는 4개라는 것을 알 수 있다. 이렇게 약수의 개수는 나누기를 활용해서 구하는데, 다만 숫자가 클 경우에는 약수의 개수를 구하기가 힘들어진다.예를 들어 숫자 512의 약수는 몇 개일까? 아마도 구하기가 힘들 것이다. 왜냐하면 숫자 8의 경우에는 나누기를 몇 번만 하면 되지만, 숫자 512의 경우에는 나누기를 많이 해야 한다. 그래서 숫자가 클 경우에는 약수의 개수를 구하기가 힘든데, 다만 이때 소인수분해를 활용하면 약수..