Pagini recente » Cod sursa (job #1190341) | Cod sursa (job #42925)
Cod sursa(job #42925)
#include <fstream.h>
int p[1005], q[1005], dim;
void desc(int n)
{
int i;
dim=0;
if(n%2==0)
{
dim++;
p[dim]=2;
q[dim]=0;
while(n%2==0)
{
q[dim]++;
n=n/2;
}
}
if(n%3==0)
{
dim++;
p[dim]=3;
q[dim]=0;
while(n%3==0)
{
q[dim]++;
n=n/3;
}
}
for(i=4;i*i<=n;i=i+3)
{
if(n%i==0)
{
dim++;
p[dim]=i;
q[dim]=0;
while(n%i==0)
{
q[dim]++;
n=n/i;
}
}
}
for(i=5;i*i<=n;i=i+3)
{
if(n%i==0)
{
dim++;
p[dim]=i;
q[dim]=0;
while(n%i==0)
{
q[dim]++;
n=n/i;
}
}
}
if(n!=1)
{
dim++;
p[dim]=n;
q[dim]=1;
}
}
unsigned long long putere(int b, int p)
{
int i;
unsigned long long ret;
ret=1;
for(i=1;i<=p;i++)
{
ret=ret*b;
}
return ret;
}
unsigned long long calc(void)
{
int i;
unsigned long long ret;
ret=1;
for(i=1;i<=dim;i++)
{
ret=ret*putere(p[i], q[i]-1)*(p[i]-1);
}
return ret;
}
int main (void)
{
int i, n;
unsigned long long ret;
ifstream fin("fractii.in");
fin>>n;
fin.close();
ret=0;
for(i=1;i<=n;i++)
{
desc(i);
ret=ret+calc();
}
ofstream fout("fractii.out");
fout<<(2*ret-1)<<"\n";
fout.close();
return 0;
}