Cod sursa(job #461886)
| Utilizator | Data | 8 iunie 2010 22:56:46 | |
|---|---|---|---|
| Problema | Fractii | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.58 kb |
#include<fstream.h>
short ciur[1000001];
long a[80000];
long n,i,j,m,aux;
long long sum,c,p;
int main()
{
ifstream f("factii.in");
ofstream g("fractii.out");
f>>n;
for (i=2;i<=n;i++)
{
if (ciur[i]==0) for (j=i+i;j<=n;j+=i) ciur[j]=1;
a[m++]=i;
}
sum=1;
for (i=2;i<=n;++i)
{
if (ciur[i]==0) sum+=(i-1)*2;
else
{
aux=i;
for (j=0;j<m,aux>1;j++)
{
p=1;
while(aux%a[j]==0)
{
aux=aux/a[j];
p*=a[j];
}
c=p*(a[j]-1)/a[j];
}
sum+=c*2;
}
}
g<<sum<<"\n";
f.close();
g.close();
}
