Pagini recente » Borderou de evaluare (job #2113602) | Cod sursa (job #1307054) | Cod sursa (job #1324532)
#include <stdio.h>
#define NMAX 1000000
int minp[NMAX + 1], phi[NMAX + 1];
void preproc()
{
/// minp
minp[1] = 1;
int i, j;
for (i = 2; i <= NMAX; i++) {
if (minp[i] == 0) {
for (j = i; j <= NMAX; j += i) {
if (minp[j] == 0) {
minp[j] = i;
}
}
}
}
/// phi
phi[1] = 1;
for (i = 2; i <= NMAX; i++) {
if (i % (minp[i] * minp[i]) == 0) {
phi[i] = phi[i / minp[i]] * minp[i];
} else {
phi[i] = phi[i / minp[i]] * (minp[i] - 1);
}
if (i <= 20) {
printf("%d %d\n", i, phi[i]);
}
}
}
int main()
{
FILE *fin, *fout;
fin = fopen("fractii.in", "r");
fout = fopen("fractii.out", "w");
preproc();
int N;
fscanf(fin, "%d", &N);
long long cnt = 0;
int i;
for (i = 1; i <= N; i++) {
cnt += phi[i];
printf("%d ", phi[i]);
}
fprintf(fout, "%lld\n", 2 * cnt - 1);
fclose(fin);
fclose(fout);
return 0;
}