Cod sursa(job #1492278)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 27 septembrie 2015 15:27:25
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>
#include <cstring>

using namespace std;

struct prim{
int factor;
int putere;
};

vector <prim> factori;
ifstream in("fractii.in");
ofstream out("fractii.out");
bool *table;

void factori_primi(int x)
{
    int p = 2;
    prim a;
    while(x!=1)
    {
        int nr = 0;
        while(x%p==0)
        {
            nr++;
            x/=p;
        }
        if(nr!=0)
        {
        a.factor = p;
        a.putere = nr;
        factori.push_back(a);
        }
        p++;
    }
}

int indicator_euler(int x)
{
    int indicator = 1;
    for(unsigned int i=0;i<factori.size();i++)
        indicator*=(factori[i].factor-1)*pow(factori[i].factor,factori[i].putere-1);
    factori.clear();
    return indicator;
}

void ciur_erastotene(int x)
{
    int sqr = sqrt(x);
    table = new bool[x+1];
    memset(table,0,sizeof(bool)*(x+1));
    for(int i=2;i<=sqr;i++)
    {
        if(!table[i])
        {
            for(int k = i*i;k<=x;k+=i)
                table[k] = true;
        }
    }
}

int main()
{
    int  n;
    in>>n;
    in.close();
    ciur_erastotene(n);
    long long int nr_fractii = 1;
    for(int i=2;i<=n;i++)
       {
           if(!table[i])
            nr_fractii+=(i-1)*2;
        else
        {
            factori_primi(i);
            int indicator = indicator_euler(i);
            nr_fractii+=indicator*2;
        }

        }
    out<<nr_fractii;
    out.close();
}