1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long LL;
const LL INF = ~0uLL>>3;
queue<int> Q;
namespace Flow {
    struct edge_type {
        int to, next;
        LL r, c;
    } edge[2000050];
    int cnte = 1, h[200005];
    void ins(int x, int y, LL r, LL c) {
        edge[++cnte].to = y; edge[cnte].next = h[x]; edge[cnte].r = r; edge[cnte].c = c; h[x] = cnte;
        edge[++cnte].to = x; edge[cnte].next = h[y]; edge[cnte].r = 0; edge[cnte].c = -c; h[y] = cnte;
    }
    int n, m, S, T;
    int pre[200005];
    LL dis[200005], a[200005];
    bool vis[200005];
    bool SPFA(LL &flow, LL &cost) {
        for (int i = S; i <= T; ++i) {
            dis[i] = INF;
            vis[i] = false;
        }
        a[S] = INF; dis[S] = 0; Q.push(S); vis[S] = true;
        int now;
        while (!Q.empty()) {
            now = Q.front(); vis[now] = false; Q.pop();
            for (int i = h[now]; i; i = edge[i].next) {
                if (!edge[i].r) continue;
                if (dis[edge[i].to] > dis[now] + edge[i].c) {
                    pre[edge[i].to] = i;
                    dis[edge[i].to] = dis[now] + edge[i].c;
                    a[edge[i].to] = min(a[now], edge[i].r);
                    if (!vis[edge[i].to]) {
                        vis[edge[i].to] = true;
                        Q.push(edge[i].to);
                    }
                }
            }
        }
        if (dis[T] >= 0)
            return false;
        flow += a[T];
        cost += a[T] * dis[T];
        for (now = T; now != S; now = edge[pre[now]^1].to) {
            edge[pre[now]].r -= a[T];
            edge[pre[now]^1].r += a[T];
        }
        return true;
    }
    LL MCMF() {
        LL flow = 0, cost = 0;
        while (SPFA(flow, cost));
        return cost;
    }
}
using Flow::ins;
using Flow::MCMF;
using Flow::S;
using Flow::T;
int N;
int P[200005], vis[200005], tot = 0, P2, P3;
void GetPrime() {
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) {
            P[++tot] = i;
        }
        for (int j = 1; j <= tot && (LL)P[j] * i <= N; ++j) {
            vis[P[j] * i] = true;
            if (i % P[j] == 0) break;
        }
    }
}
LL Calc(int n, int x) {
    LL tmp = 1;
    while (tmp * x <= n) tmp *= x;
    return tmp;
}
LL ans = 0;
int main() {
    int i, j;
    scanf("%d", &N);
    GetPrime();
    S = 0; T = tot + 1;
    for (i = 1; i <= tot && P[i] * 2 <= N; ++i) {
        if ((LL)P[i] * P[i] <= N) {
            ins(S, i, 1, 0);
            ans += Calc(N, P[i]);
        }
        else {
            ins(i, T, 1, 0);
            ans += P[i];
        }
    }
    for (P3 = i; i <= tot; ++i) ans += P[i];
    for (P2 = 1; P2 <= tot && (LL)P[P2] * P[P2] <= N; ++P2);
    for (i = 1; i < P2; ++i)
        for (j = P2; j < P3; ++j) {
            if ((LL)P[i] * P[j] > N) break;
            LL tmp = Calc(N / P[j], P[i]) * P[j] - (Calc(N, P[i]) + P[j]);
            if (tmp > 0)
                ins(i, j, 1, -tmp);
        }
    ans -= MCMF(); ++ans;
    printf("%lld", ans);
    return 0;
}