Cod sursa(job #16159)

Utilizator gigi_becaliGigi Becali gigi_becali Data 12 februarie 2007 13:00:54
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#define maxn 1<<20

bool t[maxn];
int primes[maxn], T;
int n;

void citire()
{
	freopen("fractii.in", "r", stdin);
	scanf("%d", &n);
}

void prim()
{
	int i, j;
	for(i=4;i<=n;i+=2) t[i]=1;
	
	for(i=3;i<=n;i+=2)
		if(!t[i])
		{
			for(j=i+i;j<=n;j+=i) t[j]=1;
		}
	for(i=2;i<=n;i++) if(!t[i]) primes[++T]=i;
			
}

int tot(int k)
{
	
	int i, p=k/2;
	 double sum=k;
	
	for(i=1;i<=T;i++)
	{
		if(primes[i]>p) break;
		if(k%primes[i]==0)
		{
			sum=sum*((primes[i]-1.0)/(double)primes[i]);
		}
	}
	if(sum==k) return (int) sum-1;
	return (int) sum;
}
			

int main()
{
	citire();
	prim();
	//printf("%d\n", tot(7));
	
	long long sum=0;
	//for(int i=2;i<=n;i++) sum+=(long long)tot(i);
	sum*=2;
	sum++;
	freopen("fractii.out", "w", stdout);
	printf("%lld\n", sum);
	
	
return 0;
}