Cod sursa(job #1154011)

Utilizator accxelAlex Carp accxel Data 25 martie 2014 21:48:27
Problema Fractii Scor 30
Compilator c Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long long p[1000010];

void f(long long k)
{
    long long i,j;
    p[1]=1;
    for(i=2; i<=k; i++)
    {
        if(!p[i])
        {
            
            p[i]=i-1;
            for(j=2*i; j<=k; j+=i)
            {
                if(!p[j]) p[j]=j;
                p[j]=ceil(p[j]/(float)i)*(i-1);
            }
        }
    }
    return;
}

int main()
{
	FILE *fi, *fo;
	long long N, r=1;
	fi=fopen("fractii.in", "r");
	fo=fopen("fractii.out","w");
	fscanf(fi, "%lld", &N);
	if(N!=1)
    {
        f(N);
        for(long long i=2; i<=N; i++)
            r+=2*p[i];
    
    }
    fprintf(fo, "%d", r);
    fclose(fi);
    fclose(fo);
    return 0;

}