Cod sursa(job #21781)

Utilizator k_ounu_eddyIacob Eduard k_ounu_eddy Data 24 februarie 2007 13:46:08
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<fstream>
#include<memory.h>
using namespace std;
bool NumerePrime[1000000];
long long np[100000];

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

int main()
{long long N,rezultat=0,ElementeNp=0;
fin>>N;
memset(NumerePrime,1,sizeof(NumerePrime));
for(long long i=2;i*i<=N;i++)
  if(NumerePrime[i])
    {
    np[ElementeNp]=i;
    ElementeNp++;
    long long j=2;
    while(i*j<=N)
      {
      NumerePrime[i*j]=0;
      j++;
      }
    }
for(long long cnt=2;cnt<=N;cnt++)
  {
  long long aux=cnt;
    for(long long contor=0;np[contor]<=cnt && contor<ElementeNp;contor++)
      {
      if(cnt%np[contor]==0)
         aux=aux*(np[contor]-1)/np[contor];
      }
  rezultat+=aux;
  }
rezultat*=2;rezultat++;
fout<<rezultat;
return 0;}