Cod sursa(job #53150)

Utilizator DastasIonescu Vlad Dastas Data 21 aprilie 2007 12:07:04
Problema Fractii Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

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

int n;
int pr[78500];

void prime()
{
    char a[1000000] = {0};

    int cnt = 1;
    int p = sqrt(n)+1;
    pr[0] = 2;
    for ( int i = 3; i <= n; i += 2 )
    {
        if ( a[i] == 0 )
        {
            pr[cnt++] = i;
            if ( i <= p )
            {
                for ( int j = (i<<1); j <= n; j += i )
                    a[j] = 1;
            }
        }
    }
}

long long tot(int x)
{
    double res = x;

    for ( int i = 0; i <= x; ++i )
        if ( pr[i] != 0 )
        {
            if ( x % pr[i] == 0 )
                res = res * (1.0-(1.0/pr[i]));
        }
        else
            break;

    return ceil(res);
}

int main()
{
    in >> n;
    prime();

    long long sol = 0;
    for ( int i = 2; i <= n; ++i )
    {
        sol += tot(i);
        //cout << tot(i) << " " << i << endl;
    }

    sol = sol*2 + 1;

    out << sol << endl;



	return 0;
}