Pagini recente » Cod sursa (job #2894416) | Cod sursa (job #356560) | Cod sursa (job #780139) | Cod sursa (job #628151) | Cod sursa (job #146978)
Cod sursa(job #146978)
# include <stdio.h>
# include <math.h>
# define IN "fractii.in"
# define OUT "fractii.out"
# define NMAX 1000001
int prime[NMAX],N;
int i,j;
void gasestePrime();
long long 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;
}
}
long long int tot(int n){
if(prime[n])
return n-1;
else
{
long long int res=n;
j=2;
while(n!=1&&j<=n){
if(n%j==0&&prime[j])
{
n=n/j;
res=(res/j)*(j-1);
while(n!=1){
if(n%j==0)
n/=j;
else break;
}
}
j++;
}
return res;
}
return 0;
}