Cod sursa(job #52176)

Utilizator znakeuJurba Andrei znakeu Data 18 aprilie 2007 00:14:25
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <stdio.h>
char v[100005];
int prim[50000];

int ciur(int n)
{
	int i,j,p=0;
	memset(v,1,100005);
	v[0]=0; v[1]=1;
	for(i=2; i<=n; i++)
	if (v[i])
	{
		prim[p++]=i;
		v[i]=i-1;
		for (j=i+i; j<=n; j+=i)
			v[j]=0;
	}
	return p;
}

int main()
{
	int n,s=0,i,p;
	
	FILE *in=fopen("fractii.in","r");
	fscanf(in,"%d",&n);
	fclose(in);
	
	p=ciur(n);

	
	for (i=2; i<n/2+1; i++)
	{
		for (j=0; j<p; j++)
			if (i*prim[j]<=n)
				v[i*prim[j]]=v[i]*prim[j];
	}
	
	for (i=2; i<n; i++)
		s+=v[i];
	s*=2;
	s++;
	
	FILE *out=fopen("fractii.out","w");
	fprintf(out,"%d\n",s);
	fclose(out);
	
	return 0;
}