Pagini recente » Cod sursa (job #992490) | Cod sursa (job #35488) | Cod sursa (job #97418) | Cod sursa (job #496949) | Cod sursa (job #145585)
Cod sursa(job #145585)
# 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;
for (j=0;j<1001;j++)
div[j]=0;
j=2;
while(n!=1){
if(n%j==0){
div[j]++;
n=n/j;
}
else
break;
}
j++;
while(n!=1&&j<=n){
if(n%j==0&&prime[j])
{
div[j]++;
n=n/j;
}
else j+=2;
}
for (j=2;j<=1000;j++)
if(div[j])
res=(res/j)*(j-1);
return res;
}
return 0;
}