Problem 3: Largest prime factor

💡 (프로젝트 오일러 3번문제) 어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.
문제출처: https://euler.synap.co.kr/problem=3

 

Python의 반복/조건문 및 소인수분해의 원리 활용하기

 

언뜻보면 단순반복으로 풀 수 있는 문제처럼 보인다.

물론, 앞선 문제에서 푼 것과 같이, 단순 반복문으로 풀 수는 있다.(컴퓨터 사양이 매우 좋고, 시간이 충분하다면…)

 

혹은, 주어진 숫자가 ‘600851475143’ 과 같은 큰 숫자가 아닌, 작은 숫자라면

단순히 반복문(for, while문)과 ‘나머지’를 구하는 수식(%)만으로 구할 수 있다.

 

다만, 문제에서 주어진 숫자가 매우 크므로, 위와 같이 단순 반복문만 활용해서는 결과 값 계산에 매우 많은 시간이 걸린다.

따라서, 소인수분해에 대한 다음과 같은 원리를 사용하는 것이 효율적이다.

 

예를들어, 168이라는 숫자를 소인수분해하여, 가장 큰 소인수를 구한다고 가정해보자.

 

최종적인 결과는 다음과 같이 나올 것이다.

 

168 = (2^3) × 3 × 7

 

위에서 알 수 있듯이, 168의 가장 큰 소인수는 ‘7’이다.

 

이를 구하기 위해 다음과 같은 방법을 사용할 수 있다.

 

1. 목표숫자인 ‘168’을 2로 나누어 떨어질 때까지 나눈다. (결과적으로 21만 남을 것이다.)
2. 2에서 숫자를 1만큼 키워서, 3으로 나누어 떨어질 때까지 나눈다. (결과적으로 7만 남을 것이다.)
3. 3에서 숫자를 1만큼 키워서, 4로 나누어 떨어질 때까지 나눈다. 나누어 떨어지지 않으면(나머지가 0이 아니면), 숫자만 1을 더 키운다.
4. 위의 과정을 반복한다.
5. 최종적으로 남는 숫자(7)이 가장 큰 소인수이다.

※ 남은 숫자보다 나눌 숫자(1씩 계속 키워가는 숫자)가 더 커지면 의미가 없으므로, 중단한다.

 

이와 같은 방법을 사용하면, 정답에 훨씬 빠르게 도달 할 수 있다.

 

정답은 아래 '더보기'를 클릭!

Answer: 6857

 

 

---

Code(Python)

#
# Problem 3. Largest prime factor
# Link : https://projecteuler.net/problem=3
#

# Define 'Cal' function to calculate result value
def Cal():
     number = 600851475143
     n = 2

     while n < number:
          if number % n == 0:
               number = number / n
          else: n += 1
     return number

if __name__ == '__main__':
     print(Cal())

 

다른풀이 방법(Python)

python Library인 Sympy를 이용하여 간단히 풀 수 있다. sympy import 후(import sympy 입력),

 

primefactors 메서드를 사용하면, 해당 숫자의 소인수들을 손쉽게 구할수 있다.

(sympy.primefactors(600851475143) 입력)