Pagini recente » Cod sursa (job #1515635) | Istoria paginii runda/eusebiu_oji_2014_cls9/clasament | Cod sursa (job #3196330) | Cod sursa (job #1701520) | Cod sursa (job #1597990)
#include <fstream>
#include <bitset>
using namespace std;
const int N=1000001;
ifstream fin("fractii.in");
ofstream fout("fractii.out");
bitset<N> v;
int p[N/3];
void ciur(int n)
{
int i,j;
for(i=3;i*i<=n;i+=2)
{
if(!v[i]) for(j=i*i;j<=n;j+=i) v[j]=1;
}
p[++p[0]]=2;
for(i=3;i<=n;i+=2)
{
if(v[i]==0) p[++p[0]]=i;
}
}
long long desc(int x)
{
long long sol=1;
for(int i=1;p[i]*p[i]<=x;i++)
{
if(x%p[i]==0)
{
int step=1;
while(x%p[i]==0)
{
step=step*p[i];
x/=p[i];
}
step=step/p[i];
step=step*(p[i]-1);
sol=sol*step;
}
}
if(x>1) sol=sol*(x-1);
return sol*2;
}
int main()
{
int n;
fin>>n;
ciur(n);
long long sol=0;
for(int i=1;i<=n;i++)
{
sol+=desc(i);
}
fout<<sol-1;
}