Cod sursa(job #1502661)

Utilizator c0mradec0mrade c0mrade Data 14 octombrie 2015 21:33:31
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>
#define MAX 1000001
using namespace std;

int n, i, j, nr, nrp, era[MAX], sh[MAX];

int main(){
    ifstream in("fractii.in");
    in>>n;
    in.close();
    i=2;nr=1;
    while(i<=MAX){
        if (era[i]==0)
            for(j=2*i;j<=MAX;j+=i)
                if (era[j]==0)
                    era[j]=i;
        i++;
    }
    for(i=2;i<=n;i++)
    {
        if (era[i]==0)
        {
            nr+=(i-1)*2;
            sh[i]=i-1;
        }
        else{
            if ((i/era[i])%era[i]==0)
                nrp=sh[i/era[i]]*era[i];
            else{
                nrp=sh[i/era[i]]*(era[i]-1);
                nr+=2*nrp;
                sh[i]=nrp;
            }
        }
    }
    ofstream out("fractii.out");
    out<<nr;
    out.close();
    return 0;
}