n, k = list(map(int, input().split()))
A = []
C = {}
a = n
mod = 10**5+3
dp = [0] * (mod+1)
for u in range(1, mod+1):
    for v in range(u, mod+1, u):
        dp[v] += u
        dp[v] %= mod

while not a in C:
    C[a] = len(A)
    A.append(a)
    a = dp[a]
if k <= len(A):
    print(A[k-1])
else:
    k -= len(A)
    le = len(A)-C[a]
    print(A[C[a]+k%le])