Cod sursa(job #865328)

Utilizator TheShadowsAlexandru Cristian TheShadows Data 26 ianuarie 2013 12:43:49
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<cstdio>
using namespace std;
int temp, a, b, sol=0; const int LIM=1000010;
int prim[LIM];
void ciur(int n){
    int d=2;
    while(d*d<=n){
        for(int i=2; i*d<=n; i++)
            prim[i*d]=1;
        d++;
        while(prim[d]==1) d++;
    }
}
void posib(int x){
    a*=x-1;
    b*=x;
}
void descomp(int n){
    int d=2, x=n;
    if(prim[x]==0){
        posib(x); return;
    }
    while(x!=1){
        while(prim[d]==1||x%d!=0) d++;
        posib(d);
        while(x%d==0) x/=d;
        d++;
    }
}
int main(){
    FILE *in=fopen("fractii.in","r"), *out=fopen("fractii.out","w");
    int n;
    fscanf(in, "%d\n", &n);
    ciur(n);
    for(int i=2; i<=n; i++){
        a=i; b=1;
        descomp(i);
        sol+=2*(a/b);
    }
    fprintf(out, "%d\n", sol+1);
    return 0;
}