Cod sursa(job #271324)

Utilizator igsifvevc avb igsi Data 5 martie 2009 09:44:51
Problema Fractii Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<fstream.h>

#define xx 1000001

ifstream fin("fractii.in");
ofstream fout("fractii.out");

char diviz[xx];
int n;

int ciur(int);

int main()
{
    fin>>n;
    
    int i,cnt=n;
    
    for(i=2;i<=n;i++)
      cnt+=ciur(i);
    
    fout<<cnt<<'\n';
    fout.close();
    return 0;
}

int ciur(int k)
{
    int i,j,cnt=1;
    
    for(i=2;i<=n;i++)
      diviz[i]=1;
    
    for(i=2;i<=n;i++)
      if(diviz[i]==1 && (!(i%k) || !(k%i)))
      {
         for(j=i;j<=n;j+=i)
           diviz[j]=0;
      }
      else
        if(diviz[i]==1)
          cnt++;
    return cnt;
}