Cod sursa(job #21697)

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

inline bool divizibilitate(long long nr,long long divizor)
{
if(nr%divizor==0)
  return 1;
else return 0;
}

int main()
{FILE *F=fopen("fractii.in","rt");
FILE *G=fopen("fractii.out","wt");
long long N,rezultat=0,cnt=0;
fscanf(F,"%lld",&N);
memset(NumerePrime,1,sizeof(NumerePrime));

for(long long i=2;i*i<=N;i++)
  if(NumerePrime[i])
    {
    np[cnt]=i;
    cnt++;
    long long j=2;
    while(i*j<=N)
      {
      NumerePrime[i*j]=0;
      j++;
      }
    }
    
for(long long a=2;a<=N;a++)
  {
  long long aux=a;
  for(long long cnt=0;cnt<=a;cnt++)
    if(a%np[cnt]==0)
      aux=(aux*(np[cnt]-1))/np[cnt];
  rezultat+=aux;
  }

rezultat*=2;rezultat++;
fprintf(G,"%lld\n",rezultat);
return 0;
}