Pagini recente » Cod sursa (job #1575624) | Cod sursa (job #3225848) | Cod sursa (job #2724549) | Cod sursa (job #761617)
Cod sursa(job #761617)
#include <cstdio>
#include <cmath>
int N, SUM;
int pow(int x, int y)
{
if (y == 0)
{
return 1;
}
if (y == 1)
{
return x;
}
if (y % 2 == 0)
{
return pow(x, y / 2) * pow(x, y / 2);
}
return pow(x, y / 2) * pow(x, y / 2) * x;
}
int prime(int x)
{
if (x % 2 == 0)
{
return 0;
}
for(int i = 3; i <= sqrt(x); i += 2)
{
if (x % i == 0)
{
return 0;
}
}
return 1;
}
int euler(int x)
{
if (x == 1)
{
return 1;
}
if (prime(x) == 1)
{
return x - 1;
}
int PRODUCT = 1;
int current = 2;
while(x > 1)
{
if (x % current == 0)
{
int count = 0;
while (x % current == 0)
{
x /= current;
count++;
}
PRODUCT = PRODUCT * (current - 1) * pow(current, count - 1);
}
current++;
}
return PRODUCT;
}
int main()
{
freopen("fractii.in", "r", stdin);
freopen("fractii.out", "w", stdout);
scanf("%d", &N);
SUM = 1; // FOR CASE: 1 / 1
for (int i = 2; i <= N; i++)
{
SUM += 2 * euler(i);
//printf("%d\n", i);
}
printf("%d\n", SUM);
return 0;
}