#include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=1000010; int x,k,m,ans,R,a[MAXN],cnt; struct node{ int x,y; }; queue<node>q,p; int sum=0; vector<int>v[MAXN]; void slv(){ x=read(),k=read(),m=read(); if(k>m){ printf("%lld",m); return; } ans=1;m--;k--; for(int i=2;i*i<=x;i++){R=i; if(x%i==0){ q.push({i,0}); if(x/i!=i)a[++cnt]=x/i; for(int j=2;j*j<=i;j++)if(i%j==0){v[i].pb(j);if(j!=i/j)v[i].pb(i/j);} v[i].pb(i); if(q.size()==m)break; } } while(cnt&&q.size()<m)q.push({a[cnt],0}),cnt--; if(q.size()<m)q.push({x,0}); int tmp=0; sum=p.size(); while(m&&k){k--; tmp=0;sum=0; bool fl=0; while(!q.empty()&&sum<m){ int now=q.front().x,wt=q.front().y;q.pop(); wt++; if(now==1){ if(wt+sum>=m){ q.push({1,m-sum-1});sum=m; } break; } if(now<=R){ for(auto o:v[now]){ if(sum+wt+1>m){ p.push({1,m-sum-1});sum=m;if(o!=now)fl=1; break; } p.push({o,wt});sum+=wt+1,wt=0; if(o!=now)fl=1; if(sum>=m)break; } if(sum>=m)break; } else{ int tmp=0; for(int i=2;i*i<=now;i++){tmp=i; if(now%i==0){ if(sum+wt+1>m){ p.push({1,m-sum-1});sum=m;fl=1; break; } p.push({i,wt});sum+=wt+1,wt=0;fl=1; if(sum>=m)break; } } if(sum>=m)break; for(int i=tmp;i>=2;i--){ if(now%i==0){ if(sum+wt+1>m){ p.push({1,m-sum-1});sum=m;fl=1; break; } p.push({now/i,wt});sum+=wt+1,wt=0;fl=1; if(sum>=m)break; } } if(sum>=m)break; if(sum+wt+1>m){ p.push({1,m-sum-1});sum=m; break; } p.push({now,wt}); sum+=wt+1;wt=0; } } while(!q.empty())q.pop(); while(!p.empty())q.push(p.front()),p.pop(); if(q.size()==1&&q.front().x==1)break; if(!fl){ while(!q.empty())ans+=q.front().x+q.front().y+k,q.pop(); break; } } while(!q.empty())ans+=q.front().y+q.front().x,q.pop(); printf("%lld",ans); } signed main(){ slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s"<<endl; // cout<<1+1+2+1+3+1+5+1+2+3+6+1+2+5+10+1+3+5+15+1+2+3+5+6+10+15+30<<endl; return 0; }