Cod sursa(job #314730)
Utilizator | Stanese Alex stanesealex | Data | 12 mai 2009 19:39:20 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include<cstdio>
#include<math.h>
#include<vector>
using namespace std;
int v[2000000];
int main()
{
int n,i,nr,j,t;
FILE *f=fopen("ciur.in","r");
FILE *g=fopen("ciur.out","w");
fscanf(f,"%d ",&n);
nr=n-1;
t=round(sqrt(n));
for (i=2;i<=t+1;i++)
{
if (v[i]==0)
{
j=i;
nr++;
while (j<=n)
{
if (v[j]==0)
{
v[j]=1;
nr--;
}
j=j+i;
}
}
}
fprintf(g,"%d",nr);
fclose(f);
fclose(g);
return 0;
}