오일러 프로젝트 03

sooopd

9년 ago

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

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

접근

문제 자체가 가장 큰 소인수를 구하는 문제이기 때문에, 쉽게 생각했을 때 “소인수 분해한 다음, 소인수 중에서 가장 큰 값을 구한다”인데, 소인수 분해를 구현하는 것이 어렵지는 않지만 귀찮으니까 이보다 간단한 방법으로 풀 수 있는 방법이 있는지 생각해보자. (글의 말미에서는 결국 소인수분해 함수를 작성하긴 할 거다.) 사실 위에서도 언급했지만, 이 문제는 인수의 개념을 묻는 문제이다. 어떤 수 n 을 p로 나눌 수 있다면 다음과 같은 수식으로 표현할 수 있다.

만약 나눠지지 않는다면, 나머지가 남을 것이고 그 때는, 와 같은 식으로 쓰게 될 것이다. 이 때, 위의 형태 (나누어 떨어지는)의 식에서 보면 p와 q는 모두 n의 인수이다. 그리고 p와 q가 같다면, p는 n의 제곱근(양의 제곱근)이며 이 때 n는 완전제곱수가 된다.

다시 문제로 돌아와보자. 만약 600851475143이 2로 나누어 떨어진다면 (물론 홀수임이 빤히 보이므로 2로 나눠지지 않는다는 건 알 수 있다.) 가 되고, 이 때 q 가 소수라면 답이 될 것이다. q가 소수가 아니라면 다시, q의 인수중에 가장 큰 소인수가 600851475143의 가장 큰 소인수가 될 것이다. 반대로 q가 2보다 작거나 같은 수 라면 여기서는 2가 그 답이 될 것이다.

그럼 가장 큰 소인수를 찾는 과정을 살펴보자.

600851475143을 N이라 하겠다.
먼저 N을 2로 나눠본다. 나눠진다면 N/2 의 가장 큰 소인수가 답이되므로, N을 N/2로 대체하여 조사한다.
N이 2로 나눠질 때까지 나눠본다. 더 이상 나눠지지 않으면 3, 5, 7, 9 등으로 (2이후에는 짝수를 선택하는 것이 별 의미는 없다.) 나누는 수를 증가시킨다.
계산을 반복하여, 인수를 만날 때마다 N은 점점 작아질 것이다.
최종적으로 나누려는 수가 N보다 커진다면, 원래의 N은 지금의 N보다 큰 인수를 갖지 않는다는 의미이고, 이는 현재의 N은 자신보다 작은 2이상의 수로 나눌 수 없는, 소인수라는 의미이다.

Swift로 다음과 같이 구현해 볼 수 있다.

func p003() {
  var number = 600851475143
  var p = 3 // number가 홀수 이기 때문에 2는 고려하지 않는다.
  while p < number {
    if number % p == 0 {
      number = number / 2
    } else {
      p += 2
    }
  }
  print(number)
}

소인수분해를 사용하여 풀기 (Python)

문제의 내용이 “소인수 중 가장 큰 수”를 구하는 것이기 때문에, 소인수분해를 적용한 후 가장 큰 소인수를 구해도 된다. 다만 소인수분해를 위한 코드가 좀 길 뿐이다. 소인수 분해와 관련해서는 다음의 내용을 고려해야 한다.

리턴타입 : 소인수와 해당 소인수의 지수를 짝짓고, 그 리스트를 만들어 리턴하기 때문에 [(Int, Int)] 타입의 배열을 리턴할 것이다. 개별 원소의 튜플은 (소인수, 지수)로 해석한다.
가장 작은 소인수부터 출발하여, 더 이상 나눌 수 없을 때까지 반복하여 나눈다. (나눠질 때마다 n은 나눈 몫으로 치환한다.) 나눈 횟수가 1이상이면 해당 소인수는 결과에 포함시켜야 한다.
2의 과정을 n이 1이 될 때까지 계속한다.

이 때 주안점은 n을 나눌 수 있는 다음번 최소 소인수를 찾는 것인데, 다음의 로직을 사용한다.

현재 사용중인 제수를 m 이라 할 때,
m이 1이면 2를 사용한다.
m이 2이면 3을 사용한다.
m이 3이면 5를 사용한다.
m이 5보다 크면 m보다 홀수 중에서 n을 나눌 수 있는 값을 찾는다. 만약 n의 제곱근보다 작은 홀수 중에서 찾을 수 없다면 n이 그 다음 소인수가 될 것이다.

물론 이 로직에서 m이 소수인지 여부는 중요하지 않다. 특정한 m이 소수가 아닌 홀수가 된다하더라도, 그 전에 n은 m의 홀수 소인수에 의해 다 나눠진 상태이기 때문에 m으로 나눠질 수가 없을 것이기 때문이다. 이상의 로직을 이용해서 파이썬으로 소인수분해 함수를 작성하면 아래와 같고, 이를 이용해서 문제를 풀 수 있다. 물론 시간 차이는 크게 나지는 않지만, 이 문제에서는 당장 소인수분해가 필요하지는 않다. (나중에 큰 수들의 약수의 개수를 구하는 식의 계산에서 요긴하게 쓰일 예정이다.)

def factorize(n: int) -> [(int, int)]:
  def helper(m):
    if m in (1, 2):
      return m + 1
    if m is 3:
      return 5
    else:
      k = m + 2
      while k * k <= n:
        if n % k is 0:
          return k
        k += 2
      return n
  result = []
  a = 1
  while n > 1:
    a = helper(a)
    e = 0
    while n % a is 0:
      n =  n // a
      e += 1
    if e > 0:
      result.append((a, e))
  return result
def p005():
  print(max(x[0] for x in factorize(600851475143)))

접근

소인수분해를 사용하여 풀기 (Python)

이 글 공유하기: