Problem 12

이전에 올렸던 글에서 그 다음으로 어려웠던..약수의 갯수가 500이 넘는 최소 값을 찾는 문제

삼각수를 구하는 방식에 약수를 구하는 반복문을 같이 쓰니 시간이 엄청 오래 걸려 값을 구하지 못했다.

좀 더 빠른 시간내에 구할 수 있는 방법은 소인수 분해를 사용하는 것이다, 그리고 삼각수를 구하는 공식을 매크로 함수를 이용해 하는 것도 좋다 이렇게 하면 컴퓨터가 연산하는 시간을 줄이는 데 도움을 준다.

소인수 분해를 통해 약수를 구하는 공식은 다음과 같다.

이를 코드로 옮기는 과정을 적어보았다.

1. 먼저 삼각수를 소인수 분해해주는 함수로 넘겨준다.

2. i=2부터 삼각수의 크기만큼 반복해 약수가 있는지 판별한다.

3. 약수라면 그 때의 i로 n을 나눠주고 지수 값을 증가시켜준다.

4. 증가시킨 지수 값에 + 1 을 더하여 count에 곱해준다(count = 1로 선언함)

5. count 를 리턴하여 메인해서 리턴된 값이 500이면 그 때의 삼각수를 출력한다.

소인수 분해를 하는 코드는 다음 블로그를 참고했다.

http://nuromancer1984.tistory.com/18

C 로 짜서 더 이해하기 좋았다