Pagini recente » Cod sursa (job #1644698) | Cod sursa (job #724743) | Cod sursa (job #725619) | Cod sursa (job #1552602) | Cod sursa (job #146957)
Cod sursa(job #146957)
# 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();
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;
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;
}