Pagini recente » Cod sursa (job #2983646) | Cod sursa (job #2507580) | Cod sursa (job #72436) | Cod sursa (job #2648619) | Cod sursa (job #2835299)
#include <stdio.h>
#include <stdlib.h>
int *getPrimeNumbersUntil(int n) {
int *array = (int *) calloc(n + 1, sizeof(int));
for (int i = 2; i <= n; ++i) {
if (array[i] == 0) {
for (int j = 2 * i; j <= n; j += i) {
array[j] = 1;
}
}
}
return array;
}
long long v4(int n) {
if (n == 1) {
return 1;
}
int *primeNumbers = getPrimeNumbersUntil(n);
primeNumbers[1] = 1;
long long fractionsCount = 1;
int primeDivisors[8];
int primeDivisorsCount = 0;
for (int num = 2; num <= n; ++num) {
primeDivisorsCount = 0;
if (primeNumbers[num] == 1) {
int clone = num;
for (int div = 2; div <= clone; ++div) {
if (primeNumbers[div] == 0) {
if (clone % div == 0) {
primeDivisors[primeDivisorsCount++] = div;
do {
clone /= div;
} while (clone % div == 0);
if (primeNumbers[clone] == 0) {
primeDivisors[primeDivisorsCount++] = clone;
break;
}
}
}
}
} else {
primeDivisors[primeDivisorsCount++] = num;
}
int product = 1;
int divProduct = 1;
for (int i = 0; i < primeDivisorsCount; ++i) {
product *= primeDivisors[i] - 1;
divProduct *= primeDivisors[i];
}
fractionsCount += 2 * num / divProduct * product;
}
free(primeNumbers);
return fractionsCount;
}
int main() {
char *inFileName = "fractii.in";
char *outFileName = "fractii.out";
FILE *in = fopen(inFileName, "r");
if (in == NULL) {
printf("Cannot open %s.\n", inFileName);
return 1;
}
FILE *out = fopen(outFileName, "w");
int n;
fscanf(in, "%d", &n);
fprintf(out, "%lld", v4(n));
fclose(in);
fclose(out);
return 0;
}