가장 큰 소인수

문제

소수란 1보다 크고 1과 자기 자신 이외의 양의 약수가 없는 정수입니다. n의 가장 큰 소인수를 구하세요. n이 소수라면 n을 반환하세요.

largest_prime_factor(n)을 구현하세요.

n: 소인수를 구할 정수입니다.

가장 큰 소인수를 반환하세요.

2 ≤ n ≤ 10¹². 입력값 1은 소인수가 없으므로 제외됩니다.

예시 1

입력:
n = 84

예상 출력:
expected = 7

입력:
long long n = 84;

예상 출력:
long long expected = 7;

입력:
long n = 84;

예상 출력:
long expected = 7;

84 = 2 × 2 × 3 × 7이므로, 가장 큰 소인수는 7입니다.

예시 2

입력:
n = 13

예상 출력:
expected = 13

입력:
long long n = 13;

예상 출력:
long long expected = 13;

입력:
long n = 13;

예상 출력:
long expected = 13;

13은 소수이므로, 자기 자신이 가장 큰 소인수입니다.

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

작은 소인수부터 먼저 제거하세요. 남은 값은 계속 줄어들 뿐이고, 마지막에 남는 인수가 정답입니다.

힌트 2

현재 남은 값의 제곱근까지만 나눠 보고, 맞아떨어지면 반복해서 나누세요.

힌트 3

작은 인수를 다 확인한 뒤에도 남은 값이 1보다 크면, 그 값은 소수이고 가장 큰 인수입니다.

예상 복잡도

시간 O(√n), 추가 공간 O(1)

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.