Pagini recente » Cod sursa (job #2400230) | Cod sursa (job #2916214) | Cod sursa (job #334903) | Cod sursa (job #732187) | Cod sursa (job #3173877)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> lp(1 + n, 0);
lp[0] = lp[1] = 1;
for (int i = 2; i * i <= n; ++i) {
if (lp[i] != 0)
continue;
for (int j = i * i; j <= n; j += i)
if (lp[j] == 0)
lp[j] = i;
}
for (int i = 2; i <= n; ++i)
if (lp[i] == 0)
lp[i] = i;
long long count = 1;
set<int> divisors;
for (int i = 2, nr; i <= n; ++i) {
nr = i;
while (nr != 1) {
divisors.insert(lp[nr]);
nr /= lp[nr];
}
int total = i;
for (int d : divisors)
total = (total / d) * (d - 1);
count += 2 * total;
divisors.clear();
}
cout << count << endl;
}
int main() {
freopen("fractii.in", "r", stdin);
freopen("fractii.out", "w", stdout);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}