Cod sursa(job #289267)

Utilizator hazegirlCatalina Predoi hazegirl Data 26 martie 2009 17:18:07
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<fstream.h>    
#include<math.h>  
int pr[101];
long n;

void primi()
{pr[1]=1;
for(long i=2;i<=n;i++)
	if(!pr[i])
		for(long j=2*i;j<=n;j+=i)
			pr[j]=1;
}


int main()
{long int i,j,nr=0,a,b,t,d;
ifstream f("fractii.in");
ofstream g("fractii.out");
f>>n;
primi();
nr=n+n/2+n%2;
for(i=3;i<=n;i++)
    if(!pr[i]) nr+=(n-n/i); else
    for(j=1;j<=n;j++)
    if(!pr[j]){if(i%j==0||j%i==0) nr++;} else
    {a=i<=j?i:j;
    b=j>=i?j:i;
     t=0;
     d=2;
    while(a%d==0)
	    {a/=d;
	    if(b%d==0) t=1;}
   for(d=3;d<=a && t==0; d+=2)
	while(a%d==0 && t==0)
	    {a/=d;
	    if(b%d==0) t=1;}
    if(t==0) nr++;
     }

g<<nr;
f.close(); g.close();
return 0; }