책 이야기

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?

삼각수 수열은 자연수를 더하면서 생성된다. 따라서, 7번째 삼각수는 1+2+3+4+5+6+7=28이다. 처음 10개 요소는 다음과 같다.

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

처음 일곱 개 삼각수의 인수를 나열해 보면,

 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

28은 처음으로 5개가 넘는 약수를 가지는 수임을 알 수 있다. 500개 약수를 가지는 첫 삼각수는 무엇인가?

--------------------------------------------------------------------------

삼각수라는 단어가 익숙하지 않았는데, 1부터 시작하는 연속된 자연수의 합을 뜻한다고 한다. 인수를 구하는 함수를 작성하고, 반복문을 통해 인수가 처음으로 500개 이상인 삼각수를 구하면 된다.

좀 더 효율적으로 구하려면, 소수인 인수의 곱으로 나타내고, 제곱수를 이용하면 된다. 5번 문제와 연관있는 부분이기도 한데, 예를 들어 28은 2²x7¹이므로 제곱수는 각각 2, 1이며, 약수의 갯수는 (2+1)(1+1)=6이 되는 특성을 활용하여 답을 구할수도 있을 것이다.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

13195의 소인수는 5, 7, 13, 29이다.

600851475143의 가장 큰 소인수는 무엇인가?

--------------------------------------------------------------------------

이렇게 큰 수가 나오기 때문에 프로그램을 작성하지 않으면 답을 구하기가 어려운 것이 프로젝트 오일러의 문제이다. 일단 소인수는 소수이면서 인수인 숫자이다. 12를 예로 들면 12를 나눌 수 있는 1, 2, 3, 4, 6, 12가 인수가 되며, 이 중 소수인 2, 3이 소인수가 된다.

간단히 생각해 보면 2가지 접근이 가능하다. 2부터 1씩 키워가면서 나눠지는 숫자(나머지가 0)이면서 소수인 숫자 중 가장 큰 수를 찾는 방법이 있고, 소수를 구해놓고 600851475143을 나눌 수 있는 가장 큰 숫자를 구하는 방법도 있다.

인수를 구하고 소수인지 판별하는 전자의 방법으로 해결했으며, 함수를 이용하여 소수 여부를 확인하였다.