#include<bits/stdc++.h> using namespace std; #define int long long int n; bool vis[10000005]; int prime[10000005],sz,ans; void init(int n){ vis[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){ prime[++sz]=i; } for(int j=1;j<=sz&&prime[j]*i<=n;j++){ vis[prime[j]*i]=1; if(i%prime[j]==0)break; } } } signed main(){ cin>>n; if(n<=1){ cout<<0; return 0; } init(n); for(int i=2;i<=sz;i++){ ans+=prime[i]-prime[i-1]; } for(int i=1;i<=n;i++){ if(!vis[i])continue; int tmp=LONG_LONG_MAX; for(int j=1;j<=sz;j++){ tmp=min(tmp,abs(i-prime[j])); } ans+=tmp; } cout<<ans; return 0; }