Cod sursa(job #2342642)

Utilizator FlorinVladutCreta Florin FlorinVladut Data 12 februarie 2019 23:25:23
Problema Fractii Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("fractii.in");
ofstream fout("fractii.out");

int n;
int mil = 1000000;
long long rez = 1;
bool ciur[1000001];

void createCiur()
{
    for(int i = 1; i <= mil; i++)
    {
        ciur[i] = true;
    }

    for(int i = 2; i <= mil/2; i++)
    {
        if(ciur[i] == true)
        for(int j = i; j <= mil / i; j++)
        {
            ciur[i * j] = false;
        }
    }
}

int f(int n)
{
     int i = 1, rez = n;


     while(n > 1)
     {
         i++;
         while(ciur[i] == false) i++;


         if(n % i == 0)
         {
             rez *= (i - 1);
             rez /= i;
         }
         while(n % i == 0)
         {
             n /= i;
         }
     }

     return rez;
}


int main()
{
    fin >> n;
    createCiur();

    for(int i = 2; i <= n; i++)
    {
        rez += 2 * f(i);
    }

    fout << rez;


    return 0;
}