Pagini recente » Cod sursa (job #944704) | Cod sursa (job #1098422) | Cod sursa (job #285252) | Cod sursa (job #1038391) | Cod sursa (job #178689)
Cod sursa(job #178689)
#include <stdio.h>
#include <bitset>
#define sqr 1024
using namespace std;
bitset <sqr>prim;
long i,j,t,q,p[500];
long n,x,r,d[20],k[20],f;
long long sum;
long power(long b,long p){
long rez=1;
while (p){
if ((long)(p&1)==1)
rez*=b;
b*=b;p>>=1;
}
return rez;
}
int main(){
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
//preproc
//numere prime;
prim.set();
prim[1]=0;
for (i=2;i<=sqr;++i)
if (prim[i]){
p[++q]=i;
t=sqr/i;
for (j=2;j<=t;j++)
prim[i*j]=0;
}
scanf("%ld",&n);
for (i=2;i<=n;++i){
x=i;
j=1;
r=0;
while (p[j]*p[j]<=x){
if (x%p[j]==0){
r++;
d[r]=p[j];
k[r]=0;
while (x%p[j]==0){
x/=p[j];
k[r]++;
}
}
j++;
}
if (x!=1){r++;d[r]=x;k[r]=1;}
f=1;
for (j=1;j<=r;j++)
f*=(d[j]-1)*power(d[j],k[j]-1);
sum=(long long)sum+2*f;
}
printf("%lld\n",sum+1);
return 0;
}