Cod sursa(job #120058)

Utilizator brancoCristian Achim branco Data 4 ianuarie 2008 02:46:46
Problema Fractii Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

unsigned char prime[1000000];
long long int tot[1000000];

int main(int argc , char *argv[]){
	long int i , j;

	FILE *f , *g;
	long long int nr=1;
	long int n , power , aux;

	prime[1]=1; // 1 if not prime , 0 if prime
	tot[1]=1;

	f=fopen("fractii.in" , "r");
	g=fopen("fractii.out" , "w");

	for(i=2 ; i < ((long int) sqrt(1000000)) ; i++){
		if(! prime[i]){
			for(j=i*2 ; j<1000000 ; j=j + i){
				prime[j]=1;
			}
		}
	}

	fscanf(f , "%ld" , &n);

	for(i=2 ; i <= n ; i++){ // all numbers 1 to n
		if(! prime[i]){
			tot[i]=i - 1;
			nr=nr + (i - 1) * 2;
		}
		else{
			j=1; //index in primes array
			while(1){
				if(i%j == 0 && ! prime[j]){
					aux=i;
					power=0;
					while(aux % j == 0){
						aux=aux / j;
						power++;
					}
					tot[i]=tot[aux] * (j - 1)
							* ((long int)pow(j , power - 1));
					nr=nr + tot[i] * 2;
					break;
				}

				j=j + 1;
			}
		}
	}

	fprintf(g , "%lld" , nr);


	fclose(f);
	fclose(g);

	return 0;
}