Pagini recente » Cod sursa (job #329410) | Cod sursa (job #2388411) | Cod sursa (job #221203) | Cod sursa (job #3228242) | Cod sursa (job #509378)
Cod sursa(job #509378)
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <bitset>
#include <vector>
using namespace std;
void doPrimes(int v[], const int n) {
int pos = 0;
short bs[1000000];
for (int i = 2; i <= 1000; i++) {
if (bs[i] == 0) {
bs[i] = 1;
int j = 2 * i;
while (j < n + 1) {
bs[j] = 1;
j += i;
}
v[pos++] = i;
// cout << i << " ";
}
}
}
long long totient(int p[], int n) {
long long t = 1;
for (unsigned int i = 0; i < 1001; i++) {
if (p[i] > n || p[i] == 0) break;
bool has = false;
while (n % p[i] == 0) {
n /= p[i];
if (!has) {
has = true;
t *= p[i] - 1;
continue;
}
t *= p[i];
}
}
return t*n;
}
int main() {
ifstream in("fractii.in");
ofstream out("fractii.out");
int n;
in >> n;
int v[1001];
doPrimes(v, n);
long long t = 1;
for (int i = 2; i <= n; i++) {
// for (int i = 2; i <= 10; i++) {
long long tot = totient(v, i);
t += tot * 2;
// cout << i << "->" << tot << " ," << t << endl;
}
cout << t;
out << t;
return 0;
}