Pagini recente » Cod sursa (job #1755642) | Cod sursa (job #2483914) | Cod sursa (job #2135812) | Cod sursa (job #2728189) | Cod sursa (job #144931)
Cod sursa(job #144931)
# include <stdio.h>
# include <math.h>
# define IN "fractii.in"
# define OUT "fractii.out"
# define NMAX 1000001
int prime[NMAX],N;
int i,j;
int div[1001];
void gasestePrime();
int tot(int n);
int main (){
gasestePrime();
FILE *in=fopen(IN,"rt");
fscanf(in,"%d",&N);
fclose(in);
FILE *out=fopen(OUT,"wt");
long long int sum=1;
if(N!=1)
for (i=2;i<=N;i++)
sum+=(long long int)2*tot(i);
fprintf(out,"%lld",sum);
fclose(out);
return 0;
}
void gasestePrime(){
for (i=0;i<NMAX;i++)
prime[i]=1;
prime[0]=prime[1]=0;
for (i=2;i<=sqrt(NMAX);i++)
if(prime[i]){
for (j=2;j<NMAX/i;j++)
prime[j*i]=0;
}
}
int tot(int n){
if(prime[n])
return n-1;
else
{
int res=n;
j=2;
while(n!=1){
if(n%j==0)
{
div[j]++;
n=n/j;
}
else j++;
}
for (j=2;j<=1000;j++)
if(div[j])
res=(res/j)*(j-1);
return res;
}
return 0;
}