Pagini recente » Cod sursa (job #843012) | Cod sursa (job #1325632) | tema | Cod sursa (job #3124266) | Cod sursa (job #2264254)
#include <stdio.h>
#define NMAX 1000000
long long int tot[NMAX + 1];
char is_not_prime[NMAX + 1];
int main()
{
FILE *fin = fopen("fractii.in", "r");
FILE *fout = fopen("fractii.out", "w");
int n;
fscanf(fin, "%d", &n);
for (int i = 2; i <= n; i += 1) {
tot[i] = 1;
}
for (int i = 2; i <= n; i += 1) {
if (is_not_prime[i]) {
continue;
}
tot[i] = i - 1;
long long int power = 1LL * i * i;
while (power <= n) {
for (long long int j = power; j <= n; j += power) {
tot[j] *= power / i * (i - 1);
}
power *= i;
}
for (long long int j = 1LL * i * i; j <= n; j += i) {
is_not_prime[j] = 1;
}
}
long long int res = 1;
for (int i = 2; i <= n; i += 1) {
res += tot[i] * 2;
}
fprintf(fout, "%lld\n", res);
return 0;
}