Cod sursa(job #2373873)

Utilizator GhitzarinoGhita Alexandru Ghitzarino Data 7 martie 2019 15:35:59
Problema Fractii Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>

using namespace std;
ifstream f("fractii.in");
ofstream g("fractii.out");
int v[1000005];
bool a[1000005];
int n,k;
void ciur()
{
    int i,j;
    for(i=2;i*i<=n;i++)
        if(a[i]==0) for(j=i*i;j<=n;j=j+i) a[j]=1;
    for (i=2;i<=n;i++) if (a[i]==0)v[++k]=i;
}
int main()
{
    int i,sol=0,nr,x,j;
    f>>n;
    ciur();
    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;
}