Pagini recente » Cod sursa (job #1474386) | Cod sursa (job #456384) | Cod sursa (job #3217250) | Cod sursa (job #120012) | Cod sursa (job #48003)
Cod sursa(job #48003)
#include<stdio.h>
#define max 1000000
int i, p, s, nr, ciur[max], vpr[100000];
long long suma;
void div(){
int j;
for (j=0;j<nr;j++)
if (i%vpr[j]==0) { p=vpr[j]; if ((i/p)%p==0) s=1; else s=0; break;}
}
int main(){
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
int j, tot[max], n;
scanf("%d",&n);
for (i=2;i*i<=max;i++)
if (ciur[i]==0){
j=2;
while (i*j<=max){
ciur[i*j]=1;
j++;
}
}
nr=0;
for (i=2;i<=max;i++)
if (ciur[i]==0) { vpr[nr]=i; nr++;}
tot[1]=1;
tot[2]=1;
tot[3]=2;
tot[4]=2;
tot[5]=4;
tot[6]=2;
tot[7]=6;
tot[8]=4;
tot[9]=6;
tot[10]=4;
for (i=11;i<=n;i++){
div();
if (s==1) tot[i]=p*tot[i/p];
else tot[i]=(p-1)*tot[i/p];
}
suma=0;
for (i=2;i<=n;i++)
suma+=tot[i];
printf("%lld",2*suma+1);
fclose(stdin);
fclose(stdout);
return 0;
}