약수를 효율적으로 구하는 방법

출처 : 효욜적인 약수 개수 구하기 알고리즘 :: 마이구미 :: 마이구미의 HelloWorld (tistory.com)

효욜적인 약수 개수 구하기 알고리즘 :: 마이구미

약수

어떤 수를 나누었을 때 나머지가 0인 수

 

글을쓰게된 이유

보통 소수를 구할 때는 에라토스테네스의 체를 사용하여 효율적으로 소수를 구할 수 있다.

하지만 약수에 대해서는 여태까지 여러문제를 풀면서 효율적으로 구하는 방법을 모르고 있었다.

그래서 좋은 알고리즘을 알려주신 블로그의 코드를 참고하여 추가적으로 설명하고자 한다.

 

약수를 구하기 위해서 흔히 사용하는 방법은 

위와같이 for문을 사용해 나누어 떨어지는 수를 구하여 약수를 알아냈다.

 

하지만 1부터 10만까지 처음 숫자부터 마지막 숫자 각각 약수를 구하라고 나온다면

이중 for문을 써야하는데 이렇게 된다면 시간복잡도는 O(N^2) 으로 10만 * 10만번 연산을 진행하게 된다.

10,000,000,000번 즉, 100억번을 연산해야하는데 무조건 시간초과가 뜰 수 밖에없다.

 

하지만 이 방법을 쓴다면 10만 * 10만의 경우는 쉽게 넘어갈 수 있다.

시간복잡는 O(nLogn)으로 더 좋은 효율을 낼 수 있다.

우선 코드를 설명하자면 예를 들어 10의 약수는 (1, 2, 5, 10) 총 4개가 있다. 이를 인지하고 위의 코드를 진행해보면

1 * 10 = 10 

2 * 5 = 10

5 * 2 = 10

10 * 1 = 10

총 10이 나올 수 있는 곱셈이 4번 나오게 된다. 그렇게 된다면 위에서 말한 약수 4개를 모두 구한 것과 마찬가지의 결과를 낸다. 이런식으로 내가 원하는 숫자까지 약수를 구할 수 있다.

 

두 번째 for문에서 i를 나눈 이유를 설명하자면 나는 10만까지 약수를 구할건데 1 * 10만, 2 * 10만, 3 * 10만... 하면서 초과된 값을 구할필요가 없기 때문에 곱해서 나온 값이 10만 까지만 나오게 코드를 작성한 것이다.

 

회고

이번기회에 약수에 대한 알고리즘을 자세히 알게 되어서 뭔가 찝찝한 기분이 모두 사라진것같다.

의외로 사소하게 여겨 지나가는 것들이 나중에 기억이 안날 때가 많기 때문에 하나하나 중요하게 

인지하고 넘어가야할 필요가 있다.

다음에는 더 효율적인 약수 알고리즘을 알아보고 싶고 에라토스테네스의 체에 대해서도 한번 글을 쓰고싶다.