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
|
#include <set> #include <ctime> #include <queue> #include <stack> #include <cmath> #include <vector> #include <bitset> #include <cstdio> #include <cctype> #include <string> #include <numeric> #include <cstring> #include <cassert> #include <climits> #include <cstdlib> #include <iostream> #include <algorithm> #include <functional> using namespace std ; #define rep(i, a, b) for (int i = (a); i <= (b); i++) #define per(i, a, b) for (int i = (a); i >= (b); i--) #define loop(v, it) for (auto it = v.begin(); it != v.end(); it++) #define cont(i, x) for (int i = head[x]; i; i = e[i].nxt) #define clr(a) memset(a, 0, sizeof(a)) #define ass(a, sum) memset(a, sum, sizeof(a)) #define lowbit(x) (x & -x) #define all(x) x.begin(), x.end() #define mp make_pair #define pb push_back #define fi first #define se second #define iv inline void #define enter cout << endl #define siz(x) ((int)x.size()) #define P(x) putchar(48 + x) typedef long long ll ; typedef unsigned long long ull ; typedef double db ; typedef pair <ll, ll> pii ; typedef vector <ll> vi ; typedef vector <pii> vii ; typedef queue <ll> qi ; typedef set <ll> si ; typedef map <ll, ll> mii ; typedef map <string, ll> msi ; const ll maxn = 1e7 + 5 ; const ll inf = 0x3f3f3f3f ; const ll iinf = 1 << 30 ; const ll linf = 2e18 ; const ll mod = 1e9 ; const db eps = 1e-16; void (int x) { cout << x << endl ; exit(0) ; } void PRINT(string x) { cout << x << endl ; exit(0) ; } void douout(double x){ printf("%lfn", x + 0.0000000001) ; } ll cnt,n,ans; ll prime[maxn],phi[maxn]; bool check[maxn]; void init() { phi[1] = 1; for(int i = 2;i < maxn; ++i) { if(!check[i]) prime[++cnt] = i,phi[i] = i - 1; for(int j = 1;j <= cnt && prime[j] * i < maxn; ++j) { check[i * prime[j]] = 1; if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j] - 1); else {phi[i * prime[j]] = phi[i] * prime[j];break;} } } } int main() { init(); scanf("%lld",&n); for(int i = 1;i <= n; ++i) phi[i] += phi[i - 1]; for(int i = 1;i <= cnt; ++i) if(prime[i] <= n) ans += 2 * phi[n / prime[i]] - 1; else break; printf("%lld",ans); return 0; }
|
近期评论