#include using namespace std; #include // #include #include // using namespace atcoder; /* alias */ using ull = unsigned long long; using ll = long long; using vi = vector; using vl = vector; using vll = vector; using vvi = vector; using vvl = vector; using vvll = vector; using vs = vector; using ld = long double; using pii = pair; using pll = pair; using vpll = vector; /* define short */ #define pb push_back #define mp make_pair #define all(obj) (obj).begin(), (obj).end() #define YESNO(bool) \ if (bool) { \ cout << "YES" << endl; \ } else { \ cout << "NO" << endl; \ } #define yesno(bool) \ if (bool) { \ cout << "yes" << endl; \ } else { \ cout << "no" << endl; \ } #define YesNo(bool) \ if (bool) { \ cout << "Yes" << endl; \ } else { \ cout << "No" << endl; \ } /* REP macro */ #define rep(i, a, n) for (ll i = (a); i < (ll)(n); ++i) #define reps(i, a, n) for (ll i = (a); i <= (ll)(n); ++i) template inline bool chmax(T& a, const T b) { if (a < b) { a = b; return true; } return false; } // 座標を表す構造体 struct Point { int y, x; // コンストラクタを追加 Point(int y_ = 0, int x_ = 0) : y(y_), x(x_) {} // < bool operator<(const Point& other) const { if (y != other.y) return y < other.y; return x < other.x; } // == 一致確認 bool operator==(const Point& other) const { return y == other.y && x == other.x; } }; /* エラトステネスの篩 O(N)未満で素数判定を行う N以下の整数に対して素数判定 nが素数ならば isp(n)=true、そうでなければ isp(n)=false 参考: https://qiita.com/sakofsuken/items/210e082169daba690570 */ ll sum = 0; ll upper; const ll N = pow(10, 5); vector isp(N + 1, true); // vll add_list; void sieve() { isp[0] = false; isp[1] = false; for (long long i = 2; pow(i, 2) <= N; i++) { if (isp[i]) { for (long long j = 2; i * j <= N; j++) isp[i * j] = false; // nの累乗の総和をとる for (long long j = i * i; j <= upper; j *= i) { sum += j; // add_list.pb(j); } } } } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> upper; sieve(); cout << sum << endl; return 0; }