#include <bits/stdc++.h> using namespace std; #define ll long long //#define DBG bool g_bVal[10000005] = {true, true}; vector<ll> g_vecA; int main() { #ifdef DBG freopen("min.in", "r", stdin); freopen("min.out", "w", stdout); #endif ll llN = 0; cin >> llN; for (ll i = 2; i <= llN; i++) { if (!g_bVal[i]) { for (ll j = i; i*j <= llN; j++) { g_bVal[i*j] = true; } } } for (ll i = 2; i<= llN; i++) { if (g_bVal[i]) { g_vecA.push_back(i); } } if (g_vecA.empty()) { cout << "0" << endl; return 0; } ll llSum = 0; for (ll i = 0; i < g_vecA.size()-1; i++) { llSum += g_vecA[i+1] - g_vecA[i]; } for (ll i = 2; i <= llN; i++) { if (g_bVal[i]) { continue; } auto aT = lower_bound(g_vecA.begin(), g_vecA.end(), i); ll llMin = 1e9; if (aT != g_vecA.end()) { llMin = *aT-i; } if (aT != g_vecA.begin()) { llMin = min(llMin, i - *prev(aT)); } llSum += llMin; } cout << llSum << endl; #ifdef DBG fclose(stdin); fclose(stdout); #endif return 0; }