3. Largest prime factor

projecteuler.net/problem=3

Problem 3 - Project Euler

 

 

문제는 다음과 같습니다.

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

What is the largest prime factor of the number 600851475143 ?

주어진 숫자의 약수 중 소수를 찾고, 찾은 소수 중 가장 큰 값을 구하라는 문제입니다.

이번 문제 또한, 다른 알고리즘 전략을 이용할 필요까지는 없어보여서 brute force방식으로 풀었었습니다.

 

풀이 과정은 다음과 같습니다.

1. 주어진 숫자의 약수를 구해 배열에 넣어놓는다.

2. 약수 배열을 차례로 순회하면서 소수인지를 판단한다.

  2-1. 소수일경우 변수에 기록해 둔다.

  2-2. 소수가 아닐경우 배열의 다음 숫자로 넘어간다.

3. 배열을 전부 순회하였다면, 최대 소수가 기록되어있는 변수를 출력한다.

 

코드는 아래와 같습니다.

 

import math

num=600851475143

# calc trivial divisors
def calcTrivDivNums(n) :
    arr= []
    e = int(math.sqrt(num))
    
    for i in range(1, e) :
        DividedNum, ModeNum = divmod(num,i)
        if ModeNum==0 :
            arr.append(i)
            arr.append(DividedNum)
    arr.sort()

    return arr


arr = calcTrivDivNums(num)

# check trival divisors
print(arr)

for i in arr :
        isprime = 1
        # check prime number
        e = int(math.sqrt(i))
        for j in range(2, e) :
        	# if number is prime number
            if i%j == 0 :
                isprime=0
                break
                
        # if number is not prime number
        if isprime == 1:
            #print(Max)
            Max = i
            
        
print(Max)

 

 

아래의 블로그에서는 산술의 기본정리(fundamental theorem of arithmetic)를 이용하여 조금더 효율적으로 문제를 해결하였습니다.

www.mathblog.dk/project-euler-problem-3/

Solution to Project Euler problem 3 in C# | MathBlog

 

산술의 기본정리는 다음과 같습니다.

en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

 

소수의 집합을 P ⊂ Z 라고 한다. 산술의 기본 정리에 따르면, 임의의 양의 정수 n ∈ Z 에 대하여, 곱하여 n이 되는 소수의 유한 중복집합이 유일하게 존재한다. 간단하게 말하면, 12 = 2^2 * 3, 18 = 2 * 3^2, ..., 등과 같이 숫자 n을 소수의 곱으로 나타내었을 때의 중복집합은 유일하다는 뜻이다.

     * 중복집합 : 수학에서, 중복집합(重複集合, 영어: multiset) 또는 다중집합(多重集合)은 집합에서 중복 원소를 허용하여 얻는 개념이다. 중복집합의 원소의 중복도(重複度, 영어: multiplicity)는 그 원소가 중복되는 횟수이다. 중복집합에 대하여 일반 집합과 비슷한 연산들을 정의할 수 있다.

ko.wikipedia.org/wiki/%EC%A4%91%EB%B3%B5%EC%A7%91%ED%95%A9

 

즉, 우리가 수학시간에 흔히 하던 소인수분해를 이용하겠다는 뜻인것 같습니다.

 

소인수 분해를 하면서 나누는 수(D)와 나머지(R)중 큰 수를 출력하면 되는 방식으로 문제를 풀어놓은 것을 확인할 수 있습니다. 코드는 해당 블로그에서 확인하시면 좋을것 같습니다.