Problem_012_Highly divisible triangular number

[그림 01] Problem 012 문제

문제 설명

문제 이름 : 많이 나누어지는 삼각수

문제 내용 : 삼각수는 자연수를 더해서 생성되는 숫자입니다. 예로 7번째의 삼각수를 구해보면 1 + 2 + 3 + 4 + 5 + 6 + 7을 계산하여 28이라는 숫자가 나옵니다. 그리고 28은 1, 2, 4, 7, 14, 28 이라는 6개의 약수를 가집니다. 그렇다면, 5개 이상의 약수를 가지는 숫자 중 가장 작은 삼각수는 28이라는 말이 됩니다. 이러한 조건으로 500개 이상의 약수를 가지는 가장 작은 삼각수를 구하십시오.

문제의 내용을 자세히 읽어보고 조건을 보도록 합시다.

1. 계산을 할 때마다 삼각수를 구해야 합니다.(ex> n번째 삼각수는 1+2+3+4+.....+n-1+n 임)

2. 약수를 구하는 알고리즘을 적용해야 합니다.

제가 처음에 소스코드를 작성할 때 계산할 때마다 삼각수를 구하여 계산하지 않고 1씩 증가시키는 바람에 굉장히 난해한 문제인가... 했습니다. 흑흑...

다음부터는 문제를 좀 더 자세히 읽어보고 해야겠습니다. 좋은 경험을 했습니다.

자 이제 본격적으로 소스코드를 보도록 합시다.

소스코드

- vol 01

첫번째 소스는 매우 단순하게 작성해보았습니다.

#Problem 012 Highly divisible triangular number
#python 3 version source

#the first triangle number to have over five hundred divisors

def getTriangleNum():
	triangleNum = 28
	next = 8
	count = 0
	
	while True:
		for i in range(1, triangleNum+1):
			if triangleNum % i == 0:
				count += 1
		
		if count >= 500:
			break
			
		count = 0
		triangleNum += next
		next += 1
	
	return triangleNum
	

if __name__ == "__main__":
	Main_triangleNum = getTriangleNum()
	print(Main_triangleNum)

위의 소스는 7번째부터 구해진 삼각수의 약수를 구하는 알고리즘입니다.

아주 단순하게 이루어진 소스코드로써, 1 ~ 삼각수 만큼 나눠보고 약수를 구합니다.

그리고 triangleNum에는 다음 삼각수가 되기 위한 next를 더하고, next는 += 1을 해주어 그 다음의 삼각수를 기약합니다.

위의 소스는 계산이 매우 많이 이루어지기 때문에 비효율적입니다... 계산을 엄청 많이 하게 될 것이고, 아마 하루종일 해도 답이 나오지 않을 것으로 예상됩니다.

- vol02

두번째 버전의 소스는 첨부하지 않겠습니다.

위의 소스에서 소수를 모두 제외한 계산을 해보도록 하기 위해 sieve를 첨가하였습니다. 그러나 계산의 가지수는 조금 줄어들 뿐 달라지는 건 거의 없었습니다.

- vol03

세번째 버전의 소스는 다음과 같은 알고리즘을 적용했습니다.

좀 더 효율적인 계산을 위해 미리 약수를 구하는 좋은 수학을 적용시켜 보았습니다.

알고리즘에 대한 설명은 [그림 02]와 같습니다.

[그림 02] 약수 구하는 효율적인 알고리즘

이제 이 알고리즘을 이용하여 소스코드를 작성하면 다음과 같습니다.

#Problem 012 Highly divisible triangular number
#python 3 version source

#the first triangle number to have over five hundred divisors

import math

def getTriangleNum():
	triangleNum = 28
	next = 8
	divisor = []
	
	while True:
		for i in range(1, int(math.sqrt(triangleNum))+1):
			if triangleNum % i == 0:
				divisor.append(i)
			
		if len(divisor) >= 250:
			break
		
		divisor = []
		triangleNum += next
		next += 1
	
	return triangleNum, divisor
	

if __name__ == "__main__":
	Main_triangleNum, d = getTriangleNum()
	print(Main_triangleNum, d)

소스를 설명하자면, 기존의 1 ~ 삼각수까지 range로 잡았다면 범위를 1 ~ log(n)까지 잡았습니다.

그리고 약수의 개수가 500개 이상임을 체크하기 위해서는 그의 절반인 250개 이상으로 보면 됩니다.

vol03의 소스는 5.54초 가량 걸렸습니다.

vol03과 vol01의 계산 효율은 n과 log(n)의 차이입니다.... 훨씬 차이 많이 납니다.

아, 그리고 이번에는 s-anand에서 소스코드를 첨부하지 않을 생각입니다.

이전의 소스코드에도 있었듯이, prime이라는 모듈을 첨부하여 계산하였습니다. prime이라는 모듈은 찾을 수가 없더군요...

그래서 어차피 설명도 이해도 할 수 없는 소스코드니깐 첨부하지 않을 것입니다.