Cod sursa(job #146957)

Utilizator pitbullpitbulll pitbull Data 2 martie 2008 14:10:52
Problema Fractii Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.17 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;
int div[1001];

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;
			
			for (j=0;j<1001;j++)
				div[j]=0;
			
			j=2;
				
			while(n!=1){
				if(n%j==0){
					div[j]++;
					n=n/j;
				}
				else
					break;
			}
			
			j++;
			
			while(n!=1&&j<=n){
				if(n%j==0&&prime[j])
					{
						div[j]++;
						n=n/j;
					}
				else j+=2;	
			}
			
			for (j=2;j<=1000;j++)
				if(div[j])
					res=(res/j)*(j-1);
			return res;
		}
	return 0;
}