Pagini recente » Cod sursa (job #2452970) | Cod sursa (job #2358595) | Cod sursa (job #1948402) | Cod sursa (job #11313) | Cod sursa (job #2577101)
#include <bits/stdc++.h>
using namespace std;
int n,v[100005],s,kontor,p;bitset <1000007> prime;
int putere (int a, int b) {
p=1;
for(int i=0;b>0;++i) {
if((b & (1<<i))!=0)
b^=(1<<i),p*=a;
a=a*a;
}
return p;
}
int fi (int nr) {
s=1;
for(int i=1;nr>1;++i) {
if(nr%v[i]==0) {
kontor=0;
while(nr%v[i]==0)
++kontor,nr/=v[i];
s=s*(v[i]-1)*putere(v[i],kontor-1);
}
}
return s;
}
int main () {
long long ans=1;
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
scanf("%d", &n);prime[0]=1;prime[1]=1;
for(int i=2;i<=n;++i)
if(prime[i]==0) {
v[++v[0]]=i;
for(int j=2;i*j<=n;++j)
prime[i*j]=1;
}
for(int i=2;i<=n;++i)
ans=ans+2LL*(long long)fi(i);
printf("%lld", ans);
return 0;
}