Cod sursa(job #2590436)

Utilizator Andrei1Mariciuc Andrei-Alexandru Andrei1 Data 27 martie 2020 22:11:46
Problema Fractii Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <bits/stdc++.h>

using namespace std;
//phi cate numere de la 1 la n sunt coprime cu n!
int main()
{
    freopen("fractii.in","r",stdin);
    freopen("fractii.out","w",stdout);
   int n;
    cin>>n;
    vector<int> phi(n+1);
    for(int i=0; i<=n; i++)
        phi[i]=i;
    for(int i=2; i<=n; i++)
    {
        if( phi[i] == i )//este prim
        {
            for(int j=i; j<=n; j+=i)
            {
                phi[j]/=i;
                phi[j]*=(i-1);
            }
        }
    }
    int suma=0;
    for(int i=1; i<=n; i++)
        suma+=2*phi[i];
    cout<<suma-1;
    return 0;
}