Cod sursa(job #2781023)
Utilizator | Camburu Luca AswVwsA | Data | 8 octombrie 2021 12:30:11 |
---|---|---|---|
Problema | Fractii | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.53 kb |
#include <fstream>
//#include <iostream>
using namespace std;
ifstream cin("fractii.in");
ofstream cout("fractii.out");
const int NMAX = 1e6;
int phi[NMAX + 3], i, j;
void ciur()
{
for (i = 2; i <= NMAX; i++)
phi[i] = i;
for (i = 2; i <= NMAX; i++)
if (phi[i] == i)
for (j = i; j <= NMAX; j += i)
phi[j] = phi[j] / i * (i - 1);
}
int main(){
ciur();
int n;
long long ans = 1;
cin >> n;
for (i = 2; i <= n; i++)
ans += 2 * phi[i];
cout << ans;
}