Cod sursa(job #2373834)

Utilizator NaeMihneaNae Mihnea Sebastian NaeMihnea Data 7 martie 2019 15:28:27
Problema Fractii Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
using namespace std;
ifstream f("fractii.in");
ofstream g("fractii.out");
unsigned long long n,i,j,v[3201],nr,x,k,sol;
bool a[3201];
int main()
{
    f>>n;
    for(i=2;i*i<=n;i++)
        if(!a[i])
        for(j=2;j*i<=n;j++)
            a[i*j]=1;
    for(i=2;i<=n;i++)
        if(!a[i])
        v[++k]=i;
    for(i=2;i<=n;i++)
    {
        nr=i;
        x=i;
        j=1;
        while(v[j]*v[j]<=x && x>1)
        {
            if(x%v[j]==0)
            {
                while(x%v[j]==0)
                    x/=v[j];
                nr=nr*(v[j]-1)/v[j];
            }
            j++;
        }
        if(x>1)
            nr=nr*(x-1)/x;
        sol+=2*nr;
    }
    g<<sol+1;
    return 0;

}