Pagini recente » Cod sursa (job #789197) | Cod sursa (job #1376393) | Cod sursa (job #1093459) | Cod sursa (job #435953) | Cod sursa (job #280728)
Cod sursa(job #280728)
#include <stdio.h>
#define MAX_UL 0xffffffff
bool sir[1000001];
int t[1000001];
int main ()
{
long long nrfractii;
unsigned int i ,j, q, n;
freopen("fractii.in", "r", stdin);
freopen("fractii.out", "w", stdout);
scanf("%d", &n);
nrfractii=1;
t[1]=1;
for(i=2;i<=n;i++)
{
if(sir[i]==0)
{
t[i]=i-1;
for(j=i*i; j<=n && j<MAX_UL/i; j*=i)
{
t[j]=t[j/i]*i;
}
for(j=i*2; j<=n; j+=i)
{
sir[j]=1;
for(q=i; q<MAX_UL/i && q<=n && j%q==0; q*=i)
if(!t[j] && (j/i)%q!=0)
t[j]=t[q]*t[j/q];
}
}
nrfractii+=2*t[i];
}
printf("%lld", nrfractii);
return 0;
}