Cod sursa(job #2047583)

Utilizator lessanleonard savu lessan Data 25 octombrie 2017 00:00:51
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
using namespace std;
bool verifPrim[1000001];
int prime[78499];
int main(){
    freopen("fractii.in","r",stdin);
    freopen("fractii.out","w",stdout);
    int n,k=1,i,j,ci;
    long long nr_fractii_tot,nr_fractii;
    scanf("%d",&n);
    prime[1] = 2;
    for(i=3;i<=1000000;i+=2){
        if(verifPrim[i] == 0){
            prime[++k] = i;
            j=3;
            while(i*j<=n){
                verifPrim[i*j] = 1;
                j+=2;
            }
        }
    }
    nr_fractii_tot = 1;
    for(i=2;i<=n;i++){
        ci = i;
        j=1;
        nr_fractii = i;
        while(ci != 1){
            if(ci%prime[j] == 0){
               while(ci%prime[j] == 0){
                    ci /= prime[j];
                }
                nr_fractii /= prime[j];
                nr_fractii *= prime[j]-1;
            }
            j++;
        }
        nr_fractii_tot += nr_fractii*2;
    }
    printf("%lld",nr_fractii_tot);
    return 0;
}