Cod sursa(job #2835299)

Utilizator ciprian.morosanuCiprian Morosanu ciprian.morosanu Data 18 ianuarie 2022 14:46:58
Problema Fractii Scor 80
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#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;
}