두 개의 양수 값 n과 k가 있다고 가정합니다. 이제 오름차순으로 정렬된 n의 모든 요소 목록이 있다고 가정하고 이 목록에서 k번째 요소를 찾아야 합니다. k개 미만인 경우 -1을 반환합니다.
따라서 입력이 n =28 k =4와 같으면 출력은 7이 됩니다. 28의 인수는 [1,2,4,7,14,28]이고 네 번째 인수는 7이기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
k가 1과 같으면
-
1 반환
-
-
cand :=요소가 하나인 목록 [1]
-
범위 2에서 1 + floor of(n의 제곱근)에 대해 다음을 수행합니다.
-
n mod i가 0과 같으면
-
캔드 끝에 i 삽입
-
-
m :=캔디 크기
-
-
k> 2*m 또는 (k는 2*m과 동일하고 n =(cand의 마지막 요소)^2)
-
반환 -1
-
-
k <=m이면
-
캔디 반환[k-1]
-
-
인수 :=캔드[2*m - k]
-
n/인자의 반환 몫
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
from math import floor def solve(n ,k): if k == 1: return 1 cand = [1] for i in range(2, 1+floor(pow(n, 0.5))): if n%i == 0: cand.append(i) m = len(cand) if k > 2*m or (k == 2*m and n == cand[-1]**2): return -1 if k <= m: return cand[k-1] factor = cand[2*m - k] return n//factor n = 28 k = 4 print(solve(n ,k))
입력
28, 4
출력
7