Pagini recente » Cod sursa (job #1559228) | Cod sursa (job #3193340) | Cod sursa (job #1501701) | Cod sursa (job #2248031) | Cod sursa (job #2145651)
#include <vector>
#include <fstream>
#define DMAX 1000010
std::ifstream fin("fractii.in");
std::ofstream fout("fractii.out");
int n, sol;
std::vector<int> primes;
std::vector<bool> sieve(DMAX);
int pow(int a, int b) {
if (!b)
return 1;
if (b & 1)
return a * pow(a * a, b >> 1);
return pow(a * a, b >> 1);
}
int euler(int n) {
int ind = 1;
for (int i = 0; n > 1; i++)
if (n % primes[i] == 0) {
int exp = -1;
while (n % primes[i] == 0) {
exp++;
n /= primes[i];
}
ind *= (primes[i] - 1) * pow(primes[i], exp);
}
return ind;
}
void genPrimes() {
for (int i = 2; i * i <= n; i++)
if (!sieve[i])
for (int j = i * i; j <= n; j += i)
sieve[j] = true;
primes.push_back(2);
for (int i = 3; i <= n; i += 2)
primes.push_back(i);
}
int main() {
fin >> n;
genPrimes();
sol = 1;
for (int i = 2; i <= n; i++)
sol += euler(i) << 1;
fout << sol << '\n';
fout.close();
return 0;
}