Pagini recente » Cod sursa (job #156733) | Cod sursa (job #1534079) | Istoria paginii utilizator/kuhaku | Profil NENENENE | Cod sursa (job #1774733)
#include <fstream>
#define N 1000010
using namespace std;
ifstream f("fractii.in");
ofstream g("fractii.out");
int n,p[N],e[N];
void ciur(int,int*);
long long sol;
int main()
{
int x,i,j,k;
f>>n;
ciur(n,p);
sol=1;
e[1]=1;
for(i=2;i<=n;i++)
{
j=i;
k=p[j];
x=k-1;
j/=k;
while(j%k==0)
{
x*=k;
j/=k;
}
e[i]=x*e[j];
sol+=2*e[i];
}
g<<sol;
return 0;
}
void ciur(int n,int *p)
{
int i,j,k;
for(i=2;i<=n;i+=2)
p[i]=2;
for(i=3;i*i<=n;i+=2)
if(!p[i])
{
p[i]=i;
for(j=i*i,k=2*i;j<=n;j+=k)
p[j]=i;
}
for(;i<=n;i+=2)
if(!p[i])
p[i]=i;
}