Cod sursa(job #349361)

Utilizator Teodor94Teodor Plop Teodor94 Data 19 septembrie 2009 11:10:50
Problema Ciurul lui Eratosthenes Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.43 kb
#include <cstdio>

const int N = (1<<21);

bool c[N];

int main()
{
	freopen("ciur.in","r",stdin);
	freopen("ciur.out","w",stdout);
	
	int n,j,i,nr;
	scanf("%d",&n);
	
	for (i=2;i*i<=n;++i)
	    if (!c[i])           // (!c[i])  =  (c[i]==0)   =  (c[i]!=1)    daca este prim
			for (j=i*i; j<=n; j+=i)   // j+=i  =  j=j+i
				c[j]=true;
	nr=0;
	for (i=2;i<=n;i++)
		if (!c[i]) nr++;
	printf("%d",nr);
	return 0;
}