Cod sursa(job #152936)

Utilizator drigishCiordas Dragos drigish Data 9 martie 2008 22:12:32
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<iostream>
#include<stdio.h>
using namespace std;

long long i,n,a[200000],j,nr,k,ok;


int main ()
{
     freopen("fractii.in","r",stdin);
     cin>>n;
     fclose(stdin);
     freopen("fractii.out","w",stdout);
     a[0]=1; a[1]=1;a[2]=1;
     i=2;
     for(j=2; j<=n/2; j++)
        a[i*j]=1;
     do
     {
             if (a[i]==0) 
             {
                          for(j=i; j<=n/i; j++)
                            a[i*j]=1;
             }
             i++;             
     } while(i<=n);     
     
     for(i=1; i<=n; i++)
      for(j=1; j<=n; j++)
       if((a[i]*a[j]==0 || a[i]==2 || a[j]==2) && i!=j) nr++;
       else 
       {   
       ok=0;
       if(i<j) for(k=2; k<=i/2; k++) if(i%k==0 && j%k==0) ok=1;
       if(j<i) for(k=2; k<=j/2; k++) if(i%k==0 && j%k==0) ok=1;
       if (ok==1) nr++;
       }
     cout<<nr+1;
     return 0;
}