Pagini recente » Cod sursa (job #3208101) | Cod sursa (job #1342133) | Cod sursa (job #1581992) | Cod sursa (job #2418493) | Cod sursa (job #3273795)
#include <bits/stdc++.h>
using namespace std;
ifstream in("fractii.in");
ofstream out("fractii.out");
int main() {
int n;
in >> n;
vector<int> primes({2});
vector<bool> nonPrimes(n + 1);
while (true) {
int currPrime = primes.back();
for (long long i = 1LL * currPrime * currPrime; i <= 1LL * n; i++) {
nonPrimes[i] = nonPrimes[i] || (i % currPrime == 0);
}
bool ok = false;
for (int i = currPrime + 1; i <= n; i++) {
if (!nonPrimes[i]) {
ok = true;
primes.push_back(i);
break;
}
}
if (!ok) break;
}
int sol = 1;
for (int i = 2; i <= n; i++) {
if (!nonPrimes[i]) {
sol += (i - 1) * 2;
} else {
int prod = i;
for (const auto& p: primes) {
if (i % p == 0) {
prod = prod * (p - 1) / p;
}
}
sol += prod * 2;
}
}
out << sol;
return 0;
}