Project Euler #3

Project Euler #3

---

• 문제
  
  • 풀이 1
  • 풀이 2
  • 번외
• 후기

문제

---

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의 가장 큰 소인수는 무엇인가?

풀이 1

---

• while로는 루핑시켜서 소인수 분해를 한다.(노가다)
• 구해진 소인수 중 가장 큰 수인수를 구한다.

#-*- coding: utf-8 -*-
#prime factorization
import time
num = 600851475143      #소인수 분해 대상이 되는 숫자
pf = []                 #소인수의 리스트
i = 2
stime = time.time()     #시작시간

while num > 1:
    if num % i == 0:    #나누어 떨어지는 수
        num //= i       #나눈 몫
        pf.append(i)
    else:
        i += 1

print(max(pf))          #소인수 리스트 중 최대값
print(time.time() - stime)  #소요 시간

풀이 2

---

• while을 통해 구하는 방식은 아무래도 한계가 있다.
• 우선 소수는 1과 자기 자신만을 양의 약수로 갖는 1보다 큰 자연수 이다.
• 합성수는 1과 자기 자신을 제외한 소수를 약수로 갖는 자연수 이다.
• 합성수는 다음과 같은 식으로도 표현 가능하다.
  $$n = a \cdot b \; , \quad \text{where} \quad 1 < a, b < n$$
• 그리고 이를 변형 하면 다음과 같이 된다.
  $$n =\sqrt{n} \cdot \sqrt{n}= a\cdot b \; , \text{where} \quad 1 < a \text{ OR } b \leqq \sqrt{n}$$
• 이번엔 여기서 시작한다.

#-*- coding: utf-8 -*-
#prime factorization
import time
num = 600851475143          #소인수 분해 대상이 되는 숫자
pf = []                     #소인수의 리스트
i = 2
stime = time.time()         #시작시간

while i * i <= num:         #조건만 num > 1에서 바꿨다. i <= num**0.5 등으로 바꿔도 동일하다.
    if num % i == 0:        #나누어 떨어지는 수
        num //= i           #나눈 몫
        pf.append(i)
    else:
        i += 1

if num > 1:                 #마지막 몫도 소인수이며 이때 1은 제외한다.
    pf.append(num)

print(max(pf))              #소인수 리스트 중 최대값
print(time.time() - stime)  #소요 시간

번외

---

• 실제 위 문제에서 풀이 1, 풀이 2의 실행 속도는 크게 차이가 없다.
  하지만, 소인수 분해의 대상이 되는 수가 커지면 실제 수행 시간의 차이가 비약적으로 커진다.
• 문제에 주어진 숫자(600851475143)의 마지막 자리에 3을 추가하면 6008514751433이 되며 이는 소수다.
• 6008514751433을 풀이 1, 풀이 2를 통해 소인수 분해 하면 속도 차이를 체감할 수 있다.
  

풀이 1: 일단 노트북에서는 5분이상 결과를 도출하지 못했다.
풀이 2: 1.6894862651824951(초)

후기

3번 문제 역시 난도가 높지는 않다. 다만, 수학적인 사고를 좀 더 요구하고 있다.
해당과 관련하여 시간복잡도1라는 개념이 나온다.

---

1. 시간복잡도: 알고리즘의 복잡한 정도를 수행 시간으로 나타낸 척도 ↩