Cod sursa(job #202052)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 5 august 2008 20:24:20
Problema Fractii Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<stdio.h>



char *a[1000000];

int main(){

    FILE *fin=fopen("fractii.in","r"),
        *fout=fopen("fractii.out","w");
    int N;
    long long contor=0;

    fscanf(fin,"%d",&N);
    for(int i=1;i<=N;i++)
    a[i]=new char [N];

    for(int i=2;i<=N;i++)
    for(int j=0;j<=N;j++) a[i][j]=0;

    for(int i=2;i<=N;i++)
        if(a[i][0]==0) //ciuruiesc
            for(int ii=i;ii<=N;ii+=i)
                for(int j=0;j*i<=N;j++) a[ii][(long long)i*j]=1;

    for(int i=2;i<=N;i++)
    for(int j=1;j<=N;j++) if(a[i][j]==0) ++contor;


    fprintf(fout,"%d\n",contor+N);



    fclose(fin);
    fclose(fout);

    return 0;
}