{프로젝트 오일러/Project Euler} 3. 가장 큰 소인수 구하기

한국어/Hackerrank - 한국어 버전과 문제가 다를 수 있습니다. 채점은 Hackerrank를 추천합니다.

1 <= 테스트 케이스 <= 10, 10 <= 입력값 <= 10^12

def smallest_prime(n):
    i = 3
    while i*i <= n:
        if n%i == 0:
            return i
        i += 2
    return n
for _ in range(int(input())):
    n = int(input())
    while n % 2 == 0:
        n //= 2
    while True:
        sp = smallest_prime(n)
        if sp < n:
            n //= sp
        else:
            print(n)
            break

먼저 1을 제외한 모든 자연수는 소인수 분해가 가능합니다.

그렇기에 어떤 수를 소수로 계속 나누면 결국 소수가 남게 됩니다.

전체적으로 주어진 수 N에서 N의 소인수를 구한 다음 N을 해당 소인수로 나누며 결국 자기 자신이 소수가 될 때까지 반복한다.

이때 N이 짝수인 경우 소인수를 구하는 과정에서 시작이 2가 되어야 하므로 위 코드의 i가 1씩 증가하거나 조건문을 하나 더 추가해야 합니다.

그렇기에 먼저 2로 가능한 만큼 나눈 뒤에 소인수를 구하면 i가 2씩 증가하면 됩니다. (홀수의 소인수는 홀수만 존재하기 때문)

예를 들어 232989696의 경우, 232989696은 2^10 * 3^4 * 53^2입니다.

이때 2^10은 먼저 나눠져 3^4 * 53^2인 227529가 n이 됩니다.

이때 4번 i가 3이 되어 나눠져 n은 53^2이 됩니다.

i는 53이 되어 n이 53이 되고 53은 소수이기 때문에 자기 자신을 반환하게 됩니다. (함수의 반복문은 루트 n까지만 실행)

*소인수를 찾는 과정에서 합성수가 i가 되기도 하지만 합성수는 소수의 곱으로 이루어지기 때문에 그전에 해당 수를 만드는 소수를 찾기 때문에 합성수인 약수가 i가 되는 일은 없습니다. (63의 약수 중 9가 있지만 이미 3으로 두 번 나누기 때문에 9가 반환되는 일은 없습니다.)