Daily Algorithm - Day 2

What is the largest prime factor of the number 600851475143?

600,851,475,143의 가장 큰 소인수를 구하는 문제이다.
내가 생각해낸 구현 방식은 다음과 같다.

1. 숫자 n에 대하여 약수를 배열로 출력하는 함수 구현
2. 숫자 n이 소수인지를 구분해주는 함수 구현
3. 배열 안의 소수만을 필터링하는 함수 구현 후 가장 큰 숫자(=마지막 인덱스)를 출력

그렇게 나온 코드는 아래와 같다.

//Python

# n의 약수를 전부 구하여 배열로 출력하는 함수
def div(n):
    numbers = []
    for i in range(2, n+1): 
        if n % i == 0 :
            numbers.append(i)
    return numbers
    
# n이 소수인지 확인하는 함수
def isPrime(n):
    for i in range(2, n):
        if n % i == 0:
             return False
    return True
 
# n의 약수들 중에서 소수만 filter 후 배열로 출력
def primes(n): 
    return list(filter(isPrime, div(n)))
    
print(primes(600851475143)[-1])

>>> ...

이중으로 for 문이 들어갔는데 range(2,n) 가 너무 크다보니 아무리 기다려도 답이 출력되지 않는다...
개선을 어떻게 할까 생각해보니 while을 활용해 n과 i에 대하여 나머지가 0이 나오는한 계속 나누어준다면 1개의 함수로 소인수분해를 구현하면서 처리횟수도 많이 줄일 수 있을 것 같다.

def factorize (n):
    i = 2 # 가장 작은 소수
    factors = []
    while i <= n:
        if n % i == 0:
            n = n // i
            factors.append(i)
        else:
            i += 1
    return factors
    
print(factorize(600851475143)[-1])

>>> 6857

이번엔 빠르게 답이 나왔다. 그래도 뭔가 아쉬워서 다른 사람들의 코드를 구경하다가 재밌는 코드를 발견했다.

def factorize2(n):
    factor = 1 
    while (factor <= n**0.5):  # 루트n이하인 숫자까지만
    	factor += 1
        while (n % factor == 0):  # factor가 n의 소인수라면 전부 나누고 몫을 구한다.
            n = n // factor        
    if n > 1:  # 나올 수 있는 수는 1 또는 소수 뿐이므로, 1이면 버리고 소수면 취한다.
        return n        
    return factor 
    
print(factorize2(600851475143))

>>> 6857

모든 약수에는 대칭이 되는 짝이 있으며, 짝 중에 작은 숫자는 n의 제곱근 보다 작다는 성질을 이용한 코드이다.
while 처리 횟수를 최소 n의 제곱근 만큼으로 줄일 수 있으니 이 방법 또한 효율적으로 보인다.

오늘은 여기까지

-2024.12.22-