Cod sursa(job #48031)

Utilizator andrei.12Andrei Parvu andrei.12 Data 4 aprilie 2007 12:47:53
Problema Fractii Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
#define max 1000000
int i, p, s, nr, ciur[max], vpr[100000];
long long suma;
void div(){
	int j;
	for (j=0;j<nr;j++)
		if (i%vpr[j]==0) { p=vpr[j]; if ((i/p)%p==0) s=1; else s=0; break;}
}
int main(){
	freopen("fractii.in","r",stdin);
	freopen("fractii.out","w",stdout);
	int j, tot[max], n;
	scanf("%d",&n);
	for (i=2;i*i<=max;i++)
		if (ciur[i]==0){
			//j=i+i;
			/*
			j=2;
			while (i*j<=max){
				ciur[i*j]=1;
				j++;
			}
			*/
			for(j=i+i;j<=max;j+=i)
				ciur[j]=1;
		}
	nr=0;
	for (i=2;i<=max;i++)
		if (ciur[i]==0) { vpr[nr]=i; nr++;}
	tot[1]=1;
	tot[2]=1;
	tot[3]=2;
	tot[4]=2;
	tot[5]=4;
	tot[6]=2;
	tot[7]=6;
	tot[8]=4;
	tot[9]=6;
	tot[10]=4;
	for (i=11;i<=n;i++){
		div();
		if (s==1) tot[i]=p*tot[i/p];
		else tot[i]=(p-1)*tot[i/p];
	}
	suma=0;
	for (i=2;i<=n;i++)
		suma+=tot[i];
	printf("%lld",2*suma+1);
	fclose(stdin);
	fclose(stdout);
	return 0;
}