Cod sursa(job #352008)

Utilizator adinadrian nitu adin Data 30 septembrie 2009 00:35:51
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<stdio.h>
#include<iostream.h>
long n;
long f(long k)
{
	char v[1000000]={0};
	long i,j,ret=0;
	int d=2;
	j=2;
	if(k==2) 
		return 1;
	if(!(k%2))
		while(j<k)
		{
			v[j]=1;
			j*=d;
			d++;
		}
	for(i=3;i<(k/2)+1;i+=2)
	{
		if(!(k%i))
		{
			
			d=2;
			j=i;
			while(j<k)
			{
				v[j]=1;
				j*=d;
				d++;
			}
		}
	}
	for(i=1;i<n;i++)
		if(!v[i])
			ret++;
	return ret;
}
int main()
{
	long i;
	long long fract;
	freopen("fractii.in","r",stdin);
	freopen("fractii.out","w",stdout);
	cin>>n;
	for(i=2;i<n;i++)
		fract+=f(i);
	fract*=2;fract++;
	cout<<fract;
	return 0;
}