Project Euler_ pro12

코딩 2015.01.04 10:07 |

9,10번은 쉬우니 따로 쓰진 않겠고 11번은 공부를 조금 더 한 후에 풀도록 하겠다.

Highly divisible triangular number

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

12번 문제는 위와 같다. triangle number라는 숫자에 대한 설명이 나와있고 약수가 500개가 넘는 첫번째 숫자를 구하면 되는 문제이다.

이 문제의 핵심은 triangle number를 어떻게 소인수 분해를 할것인가에 달려있다.

먼저 소인수 분해를 하려면 소수를 알아야하고 약수의 갯수는 각 소인수들의 갯수+1개의 곱으로 알아낼 수 있다.

triangle number를 쭉 써내려가다보면 triangle number를 만들어가는 과정에서 소수를 얻어낼수 있다는 것을 알 수 있다.

따라서 소수 테이블을 따로 만들어내지 않고 triangle number를 만들면서 나온 소수를 따로 저장하면 내가 필요한 소수들을 얻을 수 있을 것이라 예상하였다. 이를 바탕으로 만들어진 코드는 다음과 같다.

triangle=1
prime=[2]
for addition in range(2,13000):
num=1
triangle=triangle+addition
temp=triangle
for factor in prime:
count=0
while(not temp%factor):
temp=temp/factor
count=count+1
if(count):
num=num*(count+1)
if(temp!=1):
prime.append(temp)
if(num>=500):
print "The End"
break;
print "%d - %d의 약수의 갯수는 %d개 이다" % (addition,triangle,num)
print triangle

코드를 실행시키면 76576500이란 숫자를 얻을 수 있다.

신고

'코딩' 카테고리의 다른 글

(Algospot)Hamming Code  (0) 2015.05.20
Project Euler_ pro12  (0) 2015.01.04
Project Euler_ pro8  (0) 2014.12.29
[python] 기본문법  (0) 2013.05.08
[Matlab] Cow문제3  (0) 2013.04.16
[Java] 소켓프로그래밍  (0) 2013.03.22
Posted by MathGrammer

댓글을 달아 주세요

티스토리 툴바