Cod sursa(job #146978)

Utilizator pitbullpitbulll pitbull Data 2 martie 2008 14:36:39
Problema Fractii Scor 30
Compilator c Status done
Runda Arhiva de probleme Marime 1.02 kb
# include <stdio.h>
# include <math.h>

# define IN "fractii.in"
# define OUT "fractii.out"
# define NMAX 1000001

int prime[NMAX],N;
int i,j;


void gasestePrime();
long long int tot(int n);

int main (){
	gasestePrime();
	FILE *in=fopen(IN,"rt");
	fscanf(in,"%d",&N);
	fclose(in);
	
	FILE *out=fopen(OUT,"wt");
	long long int sum=1;
	if(N!=1)
		for (i=2;i<=N;i++)
			sum+=(long long int)(2*tot(i));
	fprintf(out,"%lld",sum);	
	fclose(out);
	
	return 0;
}

void gasestePrime(){
	for (i=0;i<NMAX;i++)
		prime[i]=1;
	prime[0]=prime[1]=0;
	for (i=2;i<=sqrt(NMAX);i++)	
		if(prime[i]){
			for (j=2;j<NMAX/i;j++)
				prime[j*i]=0;	
		}
}

long long int tot(int n){
	if(prime[n])
		return n-1;
	else 
		{
			long long int res=n;
			
			j=2;
			
			while(n!=1&&j<=n){
				if(n%j==0&&prime[j])
					{
						n=n/j;
						res=(res/j)*(j-1);
						while(n!=1){
							if(n%j==0)
								n/=j;
							else break;
						}
					}
					
				j++;	
			}
			
			return res;
		}
	return 0;
}