Home » 소인수분해

소인수분해

오일러 프로젝트 12

오일러 프로젝트의 열두번째 문제. 이번에는 약수가 500개 이상인 삼각수를 찾는 문제이다. (http://euler.synap.co.kr/prob_detail.php?id=12)

1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다.  예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다. 이런 식으로 삼각수를 구해 나가면 다음과 같습니다.
 

 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

위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다. 그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까

더 보기 »오일러 프로젝트 12

오일러 프로젝트 03

오일러 프로젝트 세 번째 문제. 이번 문제는 인수의 개념과 관련된 문제이다. 일단 문제는 다음과 같다.

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요. (http://euler.synap.co.kr/prob_detail.php?id=3)

더 보기 »오일러 프로젝트 03

소인수분해 구현하기

소인수분해(prime fatorization)는 어떤 합성수를 소인수의 곱으로 표현하는 것을 의미한다. 12는 합성수이며, 1, 2, 3, 4, 6, 12 로 나눠질 수 있다. 이렇게 어떤 합성 수를 인수의 곱으로 표시하는 방법은 다양하지만, 소수들의 곱으로 표현하는 방법은 (순서를 무시하면) 하나의 방법만 존재한다. 12 = 2 * 2 * 3 으로 표시할 수 있다.

소인수 분해를 사용하면 약수의 개수나 모든 약수의 합을 좀 더 쉽게 계산할 수 있다. 물론 이것은 연필과 종이를 사용할 때에 적용될 것 같은 이야기이다. 컴퓨터를 사용하는 소인수 분해의 경우, “소수인 인수를 정하는 것”에 제법 시간이 소요될 수 있기 때문에 실제로 그리 크지 않은 범위의 수에 대해서는 무식하게 루프를 돌면서 나눠보는 것으로 약수를 세거나 더하는 방법이 더 빠를 수 있다.

더 보기 »소인수분해 구현하기