Cod sursa(job #975051)

Utilizator stefanfStefan Fulger stefanf Data 18 iulie 2013 22:23:30
Problema Fractii Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int** sieve(int n)
{
    int **s = malloc(2 * sizeof(int*));
    s[0] = calloc((n + 2), sizeof(int));
    s[1] = calloc((n + 2), sizeof(int));

    int i,j;
    
    for (i = 2; i < n; i++)
        for (j = i; j <= n; j += i) {
	    if(s[0][j] == 0) {
		s[0][j] = i;
		s[1][j] = (i - 1);
	    } else {
		s[0][j] *= i;
		s[1][j] *= (i - 1);
	    }
	}

    return s;
}

int indicator(int** s, int ind)
{
    int i;
    int nr = ind / s[0][ind] * s[1][ind];

    return nr;
}

int main()
{
    FILE *f = fopen("fractii.in", "r");
    FILE *g = fopen("fractii.out", "w");

    int n;
    fscanf(f, "%d", &n);

    int **s = sieve(n);

    int i;
    int suma = 1;
    for (i = 2; i <= n; i ++) {
        suma += indicator(s, i) * 2;
    }

    fprintf(g,"%d\n", suma);

    fclose(f);
    fclose(g);
    free(s);
    return 0;
}