가장 큰 소인수 구하기

프로젝트 오일러 - 문제 3번

• 가장 큰 소인수 구하기

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다. 예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. 600851475143의 소인수 중에서 가장 큰 수를 구하세요.

해결방법

문제를 풀기 위해선 소수인지 아닌지 판별하는 부분이 필요해 보인다.

먼저 소수를 구하는 프로그램을 짜야겠다.

소수는 1과 자기 자신 외에 양의 약수가 없는 1보다 큰 자연수
소수는 2를 제외하고 모두 홀수

def is_prime(number):
    '''소수인지 판별'''
    if number == 1:  # 1은 소수가 아니다
        return False

    '''
    2부터 자신보다 1 작은 수(number-1)까지 나누어 떨어진다면
    이 숫자는 소수가 아니다. (자신외에는 나누어지면 안됨)
    '''
    for i in range(2, number):
        if number % i == 0:
            return False

    # 위 항목을 통과하면 소수이다.
    return True

# 테스트
for i in range(2, 50):
    print(f'{i}는 소수인가? {is_prime(i)}')

소수를 구하는 함수를 만들었으니 본격적으로 문제를 풀어보자.

def is_prime(number):
    '''소수인지 판별'''
    if number == 1:  # 1은 소수가 아니다
        return False

    '''
    2부터 자신보다 1 작은 수(number-1)까지 나누어 떨어진다면
    이 숫자는 소수가 아니다. (자신외에는 나누어지면 안됨)
    '''
    for i in range(2, number):
        if number % i == 0:
            return False

    # 위 항목을 통과하면 소수이다.
    return True

def max_prime(number):
    maximum = 0  # 최댓값을 저장할 변수
    i = 2  # 1은 소수가 아니다.

    while number >= i:
        if is_prime(i):  # 소수로만 나눈다. 맞나?
            if number % i == 0:  # 나누어 떨어진다면
                number //= i     # 나눈 몫을 number에 넣고
                maximum = i      # maximum에 소수인 i를 넣는다.
                continue         # 그리고 i를 그대로 유지하면서 계속 나눠본다.
        i += 1  # 만약 소수가 아니거나 나누어 떨어지지 않는다면 i를 증가시킨다.

    return maximum  # 최대 소수를 반환한다.

# print(max_prime(13195))
print(max_prime(600851475143)) # 6857

두 번째 함수는 소수중에서 최댓값을 구하는 함수이다.

처음에는 리스트에 저장했었으나 그러면 메모리를 많이 먹을거 같아 기존에 풀었던 방법대로 변수에 maximum을 계속 입력해 주는 방식으로 바꿨다.